## 1) Concise, abridged problem statement

You have a counter with `N` registers (positions `0..N-1`). Each register stores a digit `Ai ∈ {0,1,2}` and represents the value:

\[
\sum_{i=0}^{N-1} A_i \cdot 2^i
\]

Initially all `Ai = 0`. You must perform `M` operations; operation `p` means “add \(2^p\)” to the stored value. After each operation, output a description of the update as:

- `K` (number of changed registers, `1 ≤ K ≤ 4`)
- followed by `K` pairs `(index, new_value)` describing the registers you changed and their new values.

It’s guaranteed the total sum added never exceeds \(2^N - 1\). You must ensure each operation changes at most 4 registers.

---

## 2) Detailed editorial (how the solution works)

### Key idea: redundant binary representation
Digits are in `{0,1,2}`, so the same number can have multiple representations (e.g. `5 = (1,0,1) = (0,2,1)`). This redundancy lets us avoid long carry chains.

If we naïvely add \(2^p\) like standard binary, we may need to propagate carry through many consecutive `2`s / `1`s, changing many registers—disallowed.

So we maintain an **invariant** that prevents long carry chains.

---

### Invariant maintained
**Between any two positions containing digit `2`, there is at least one position containing digit `0`.**

Equivalently: you never have `...2 xxx 2...` with all `xxx` being only `1`s (or `2`s); there must be a `0` somewhere between.

This invariant ensures that “carry-like effects” can always be resolved locally with a small bounded number of digit changes.

---

### Data structure to support fast local decisions
We need, for a given `p`, to quickly find:

- `next_two`: the smallest index `> p` such that `reg[index] == 2` (if none exists among `0..N`, we treat a sentinel at `N+1` as a `2`)
- `prev_zero`: the greatest index `< next_two` such that `reg[index] == 0`

The solution maintains three sets:

- `pos_for_val[0]`: indices where digit is `0`
- `pos_for_val[1]`: indices where digit is `1`
- `pos_for_val[2]`: indices where digit is `2`

Each update changes only a few positions, so we can update sets in `O(log N)` per changed digit.

A sentinel `2` at position `N+1` guarantees `next_two` always exists; we never actually “output” changes for it unless needed (the code may touch `N+1`, but constraints on sum prevent overflow past `N` in valid runs; still, the array is sized safely).

---

### How to add \(2^p\) in ≤ 3 digit changes
For each query position `p`:

Let:
- `next_two = first index > p with digit 2` (via set upper_bound)
- `prev_zero = last index < next_two with digit 0` (via set lower_bound / prev)

We consider three cases:

---

#### Case 1: no zero separator between `p` and `next_two`
Condition: `next_two <= N` **and** `p >= prev_zero`.

Interpretation: from `(prev_zero+1 .. next_two-1)` there are **no zeros**, meaning the segment from `p` up to `next_two` is “dangerous” for carries. The invariant says there can’t be two `2`s without a `0` between, so this configuration is tightly constrained and can be fixed with a local “carry reroute”.

Perform 3 changes:
1. `reg[p] += 1`
2. `reg[next_two] -= 2` (so a `2` becomes `0`)
3. `reg[next_two + 1] += 1`

Why is it correct numerically?

\[
+2^p \;+\; (-2)\cdot 2^{next\_two} \;+\; 1\cdot 2^{next\_two+1}
= 2^p - 2^{next\_two+1} + 2^{next\_two+1}
= 2^p
\]

So the represented number increases by exactly \(2^p\).

Why digits stay in `{0,1,2}` and invariant holds:
- `reg[next_two]` was `2`, becomes `0`.
- `reg[p]` and `reg[next_two+1]` can’t jump beyond `2` under the invariant’s structure; the editorial comment in the code explains the subtle reasoning.

---

#### Case 2: there *is* a zero separator above `p`, and `reg[p] != 0`
Condition: `next_two > N` or `p < prev_zero` (so there exists a zero between `p` and next_two), and also `reg[p]` is `1` or `2`.

Then we can do a 2-change local rewrite:
1. `reg[p] -= 1`
2. `reg[p+1] += 1`

Numerically:

\[
-2^p + 2^{p+1} = +2^p
\]

So it’s equivalent to adding \(2^p\), but done by shifting one unit of weight upward.

---

#### Case 3: `reg[p] == 0`
Just increment it:

1 change:
- `reg[p] += 1`

This directly adds \(2^p\) with no carries.

---

### Complexity
Each operation does a constant number (≤ 3) of set insert/erase operations, each `O(log N)`. With `N ≤ 1000`, `M ≤ 10000`, this is easily fast enough.

---

## 3) C++ solution

```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 n, m;
vector<int> queries;

void read() {
    cin >> n >> m;
    queries.resize(m);
    cin >> queries;
}

void solve() {
    // The key is to maintain a register state where adding 2^p never requires
    // long carry chains. Since each register holds {0,1,2} (a redundant base-2
    // representation), the same number has many encodings and we can pick one
    // that keeps carries local. A good approach is to find some invariant that
    // will allow something like this and keep it throughout the updates.
    //
    // A good example for invariant is the following: between any two 2s there
    // is always at least one 0. This guarantees that carries can be absorbed in
    // O(1) changes per addition. The only part is that we should also make sure
    // that the invariant is kept after this addition.
    //
    // For each operation of adding 2^p, let next_two = nearest index > p with
    // reg = 2, and prev_zero = rightmost index < next_two with reg = 0. We
    // consider three cases:
    //
    //     1) p >= prev_zero (no zero between p and next_two):
    //
    //            Change: reg[p]++, reg[next_two] -= 2, reg[next_two+1]++.
    //            Net: +2^p - 2^{next_two+1} + 2^{next_two+1} = +2^p.
    //            3 changes.
    //
    //        The invariant ensures reg[p] < 2 (otherwise p and next_two would
    //        be two 2s with no 0 between them) and reg[next_two+1] < 2
    //        (adjacent to a 2), so both +1s produce <= 2. Invariant is
    //        preserved: if reg[p] becomes 2, reg[next_two] becoming 0 is the
    //        separator above. If reg[next_two+1] becomes 2 it was 1, meaning
    //        next_two was the first 2 above it, so a 0 already existed between
    //        next_two+1 and the next 2 further up. Nothing up there changed.
    //
    //   2) reg[p] != 0 (there is a zero between p and next_two):
    //
    //          Change: reg[p]--, reg[p+1]++.
    //          Net: -2^p + 2^{p+1} = +2^p.
    //          2 changes.
    //
    //      reg[p+1]++ can create a 2 at most, but prev_zero lies between p
    //      and next_two, so a 0 separator already exists nearby.
    //
    //   3) reg[p] == 0:
    //
    //          Change: reg[p]++.
    //          Net: +2^p.
    //          1 change.
    //
    //      No new 2 is created. The 0 at p can't be the sole separator between
    //      two 2s: if reg[p] == 0 then prev_zero >= p, but reaching case 3
    //      requires skipping case 1, which means either next_two > n (no 2
    //      above) or prev_zero > p (another 0 above p still separates).

    vector<int> reg(n + 2, 0);
    set<int> pos_for_val[3];
    for(int i = 0; i <= n; i++) {
        pos_for_val[0].insert(i);
    }
    pos_for_val[2].insert(n + 1);

    auto apply = [&](int pos, int delta) {
        pos_for_val[reg[pos]].erase(pos);
        reg[pos] += delta;
        pos_for_val[reg[pos]].insert(pos);
        cout << ' ' << pos << ' ' << reg[pos];
    };

    for(int p: queries) {
        int next_two = *pos_for_val[2].upper_bound(p);
        int prev_zero = *prev(pos_for_val[0].lower_bound(next_two));

        if(next_two <= n && p >= prev_zero) {
            cout << 3;
            apply(p, 1);
            apply(next_two, -2);
            apply(next_two + 1, 1);
        } else if(reg[p] != 0) {
            cout << 2;
            apply(p, -1);
            apply(p + 1, 1);
        } else {
            cout << 1;
            apply(p, 1);
        }
        cout << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys
from bisect import bisect_left, bisect_right
from sortedcontainers import SortedSet

def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    n = next(it)
    m = next(it)
    queries = [next(it) for _ in range(m)]

    # reg[i] is digit at position i, digits are always in {0,1,2}
    # size n+2 to safely use positions up to n+1 (sentinel at n+1)
    reg = [0] * (n + 2)

    # Keep positions for each digit value in a sorted set.
    # Using SortedSet (from sortedcontainers) provides:
    # - O(log N) add/remove
    # - O(log N) bisect-based successor/predecessor queries
    pos = [SortedSet() for _ in range(3)]

    # Initially reg[0..n] are 0 (include n as buffer), insert them.
    for i in range(0, n + 1):
        pos[0].add(i)

    # Sentinel "2" at n+1 so a 'next_two' always exists.
    pos[2].add(n + 1)
    reg[n + 1] = 2  # keep internal consistency (never printed)

    out_lines = []

    def apply(changes, idx, delta):
        """Update reg[idx] += delta, maintain pos sets, and record the change."""
        old = reg[idx]
        pos[old].remove(idx)          # remove from old value's set
        reg[idx] = old + delta        # update digit
        pos[reg[idx]].add(idx)        # add to new value's set
        changes.append((idx, reg[idx]))

    for p in queries:
        # next_two: smallest index > p with digit 2
        j = pos[2].bisect_right(p)
        next_two = pos[2][j]

        # prev_zero: largest index < next_two with digit 0
        k = pos[0].bisect_left(next_two) - 1
        prev_zero = pos[0][k]

        changes = []

        # Case 1
        if next_two <= n and p >= prev_zero:
            apply(changes, p, +1)
            apply(changes, next_two, -2)
            apply(changes, next_two + 1, +1)

        # Case 2
        elif reg[p] != 0:
            apply(changes, p, -1)
            apply(changes, p + 1, +1)

        # Case 3
        else:
            apply(changes, p, +1)

        # Format output: K followed by K pairs
        parts = [str(len(changes))]
        for idx, val in changes:
            parts.append(str(idx))
            parts.append(str(val))
        out_lines.append(" ".join(parts))

    sys.stdout.write("\n".join(out_lines))

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

**Note:** This uses `sortedcontainers` (third-party). If you need pure standard-library Python, tell me and I’ll provide a version using a balanced-tree alternative strategy (given `N ≤ 1000`, we can also do it with `bisect` over maintained sorted lists and accept `O(N)` updates, which is still fine here).

---

## 5) Compressed editorial

Maintain digits `reg[i] ∈ {0,1,2}` with invariant: **between any two `2`s there is a `0`**. Store positions of each value in ordered sets.

To add \(2^p\), find:
- `next_two`: nearest index `> p` with digit `2` (sentinel `2` at `n+1`)
- `prev_zero`: nearest index `< next_two` with digit `0`

Cases:
1. If `next_two ≤ n` and `p ≥ prev_zero` (no zero between `p` and that `2`): do 3 changes  
   `reg[p]++`, `reg[next_two]-=2` (2→0), `reg[next_two+1]++`. Net effect = \(2^p\).
2. Else if `reg[p] != 0`: do 2 changes  
   `reg[p]--`, `reg[p+1]++`. Net effect = \(2^p\).
3. Else: do 1 change  
   `reg[p]++`.

All operations change ≤ 3 registers (≤ 4 required), preserve digits in `{0,1,2}`, and preserve the invariant. Each update costs `O(log N)` using sets.