<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

478. Excursion
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



One day a group of students, consisting of boys (a heads) and girls (b heads), got to an idea to make an excursion led by their school teacher over the city, they lived in. At the very start of the party schoolboys went away walking separately from the teacher, rather than obedient school girls, who stayed with the teacher. Anyhow, when approaching any boutique during the excursion, some girls can leave the group to go for a fitting their lovely dresses, and they will never come back again. On the contrary, ruddy cheeked and cheered up boys can go back to the teacher and stay with him with great enjoy until the end of excursion. At some points of time scrupulous teacher recalculates the number of students in the group and writes it down in his notebook.

Now the teacher wants to evaluate the effectiveness of extracurricular work, so he askes you to find any feasible student joining/disjoining schedule.

Input
The first line of input contains two integers a and b (1 ≤ a, b ≤ 100) — the number of boys and girls respectively. The second line has the only integer n (1 ≤ n ≤ 100) — the number of notes in teacher's book. The third one contains exactly n non-negative integers not exceeding 200, denoting numbers the teacher wrote down, in the order of their appearance in the notebook.

Output
If there are any mistakes in teacher's notes, that is no feasible schedule exists, print "ERROR". Otherwise, print to output n lines. i-th line should contain two non-negative integers, denoting the number of schoolboys joined and the number of schoolgirls separated from the teacher respectively exactly before he recalculated students at i-th time. If there are multiple solutions, output any.

Example(s)
sample input
sample output
3 3
2
2 3
1 2
2 1

sample input
sample output
3 3
3
1 2 5
ERROR

sample input
sample output
2 2
1
2
0 0

<|response|>
1) Abridged problem statement

- There are a boys and b girls. Initially, 0 boys are with the teacher and all b girls are with the teacher.
- The teacher takes n notes. For each note i:
  - Before counting, some nonnegative number of boys may join (boys never leave afterward).
  - Some nonnegative number of girls may leave (girls never return).
  - Then the teacher writes the current group size.
- Given the n recorded sizes, output any sequence of moves (boys_joined_i, girls_left_i) for i = 1..n that matches the notes. If impossible, print "ERROR".


2) Key observations

- Monotonicity:
  - Boys with the teacher never decrease (only join): B_i ≥ B_{i−1}.
  - Girls with the teacher never increase (only leave): G_i ≤ G_{i−1}.
- Bounds: 0 ≤ B_i ≤ a and 0 ≤ G_i ≤ b for all i.
- Sum constraint at each recorded note: B_i + G_i = recorded_count_i.
- Convenient initialization: treat an implicit note 0 with total b (because we start with 0 boys and b girls). So cnt[0] = b and the given notes become cnt[1..n].
- Transition from step i−1 to i:
  - Let current girls be G_{i−1} = cnt[i−1] − B_{i−1}. Choose any y in [0..G_{i−1}] girls to leave.
  - Then G_i = G_{i−1} − y is fixed, so B_i = cnt[i] − G_i is determined.
  - Validity requires B_i ≥ B_{i−1}, 0 ≤ B_i ≤ a.


3) Full solution approach

- DFS over states (pos, boys):
  - pos ∈ [0..n] is how many notes have been processed.
  - boys is the number of boys with the teacher at that time.
  - visited[pos][boys] = reachable or not.
- Initialization: start DFS from (0, 0) with visited[0][0] = true (0 boys, b girls).
- Transition:
  - For each reachable state (pos, boys), compute girls = cnt[pos] − boys. If girls is outside [0..b], skip.
  - For all girls_left in [0..girls]:
    - new_girls = girls − girls_left
    - new_boys = cnt[pos+1] − new_girls
    - If new_boys ≥ boys and 0 ≤ new_boys ≤ a and not yet visited, mark visited and recurse.
    - Store a parent pointer: par[pos+1][new_boys] = (boys, new_boys − boys, girls_left).
- After DFS, if any visited[n][end_boys] is true, backtrack using parent pointers to produce the sequence of (boys_joined, girls_left) for each step. Otherwise, print "ERROR".
- Complexity:
  - States: (n+1) × (a+1) ≤ 101 × 101.
  - For each state, we try up to b options of girls leaving.
  - Time O(n · a · b) ≤ about 10^6 operations; memory O(n · a).


4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int a, b, n;
vector<int> cnt;

void read() {
    cin >> a >> b;
    cin >> n;
    cnt.resize(n);
    cin >> cnt;
    cnt.insert(cnt.begin(), b);
}

void dfs(
    int pos, int cnt_boys, vector<vector<bool>>& visited,
    vector<vector<tuple<int, int, int>>>& par
) {
    int cnt_girls = cnt[pos] - cnt_boys;
    if(cnt_girls < 0 || cnt_boys < 0 || cnt_boys > a || cnt_girls > b) {
        return;
    }

    if(pos == n) {
        return;
    }

    for(int cnt_girls_leave = 0; cnt_girls_leave <= cnt_girls;
        cnt_girls_leave++) {
        int new_cnt_girls = cnt_girls - cnt_girls_leave;
        int new_cnt_boys = cnt[pos + 1] - new_cnt_girls;
        if(new_cnt_boys >= cnt_boys && new_cnt_boys <= a &&
           !visited[pos + 1][new_cnt_boys]) {
            par[pos + 1][new_cnt_boys] = {
                cnt_boys, new_cnt_boys - cnt_boys, cnt_girls_leave
            };
            visited[pos + 1][new_cnt_boys] = true;
            dfs(pos + 1, new_cnt_boys, visited, par);
        }
    }
}

void solve() {
    // State after note i is fully determined by how many boys are currently
    // with the teacher: girls = note[i] - boys. We prepend note 0 = b (all
    // girls start with the teacher, no boys). dfs explores reachable
    // (position, boys) states: only boys join (count is nondecreasing) and
    // only girls leave (count is nonincreasing). visited[pos][boys] marks
    // reached states and par[pos][boys] stores the (prev_boys, boys_joined,
    // girls_left) transition so we can reconstruct one schedule. If any state
    // at the last note is reachable we walk the parents back; otherwise no
    // feasible schedule exists.

    vector<vector<bool>> visited(n + 1, vector<bool>(a + 1, false));
    vector<vector<tuple<int, int, int>>> par(
        n + 1, vector<tuple<int, int, int>>(a + 1, {-1, -1, -1})
    );

    dfs(0, 0, visited, par);

    for(int cnt_boys = 0; cnt_boys <= a; cnt_boys++) {
        if(visited[n][cnt_boys]) {
            vector<pair<int, int>> ans;
            int pos = n, c = cnt_boys;
            while(pos > 0) {
                auto [prev_boys, move_boys, move_girls] = par[pos][c];
                ans.push_back({move_boys, move_girls});
                c = prev_boys;
                pos--;
            }

            reverse(ans.begin(), ans.end());
            for(auto [x, y]: ans) {
                cout << x << ' ' << y << '\n';
            }
            return;
        }
    }

    cout << "ERROR" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5) Python implementation

```python
import sys

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    a = int(next(it))  # total boys
    b = int(next(it))  # total girls
    n = int(next(it))  # number of notes
    rec = [int(next(it)) for _ in range(n)]

    # Prepend the implicit initial note: starting total is b (0 boys + b girls)
    cnt = [b] + rec  # cnt[0..n]

    # dp[pos][boys] = reachable after processing pos notes with 'boys' boys
    dp = [[False] * (a + 1) for _ in range(n + 1)]
    # par[pos][boys] = (prev_boys, boys_joined, girls_left)
    par = [[None] * (a + 1) for _ in range(n + 1)]

    dp[0][0] = True  # initial: 0 boys, b girls

    for pos in range(n):
        for boys in range(a + 1):
            if not dp[pos][boys]:
                continue
            girls = cnt[pos] - boys  # must match current recorded total
            if girls < 0 or girls > b:
                continue

            # Try all numbers of girls leaving before next note
            for left in range(girls + 1):
                new_girls = girls - left
                new_boys = cnt[pos + 1] - new_girls

                # Validate: boys non-decreasing and in range
                if new_boys < boys or new_boys < 0 or new_boys > a:
                    continue

                if not dp[pos + 1][new_boys]:
                    dp[pos + 1][new_boys] = True
                    par[pos + 1][new_boys] = (boys, new_boys - boys, left)

    # Find any reachable final state
    end_boys = None
    for boys in range(a + 1):
        if dp[n][boys]:
            end_boys = boys
            break

    if end_boys is None:
        print("ERROR")
        return

    # Reconstruct actions
    actions = []
    pos = n
    boys = end_boys
    while pos > 0:
        prev_boys, joined, left = par[pos][boys]
        actions.append((joined, left))
        boys = prev_boys
        pos -= 1

    actions.reverse()
    out_lines = ['{} {}'.format(j, l) for j, l in actions]
    print('\n'.join(out_lines))

if __name__ == "__main__":
    solve()
```
