Let \(f(A)\) be the total \(\mathrm{XOR}\) or \(A\). For each query, we want to find the value of \(f(A)\) after the modification.

First, let us consider the case where type-\(2\) queries are not given. In this case, if \(f(A)\) before \(A_x\) is modified was \(X\), the value \(f(A)\) after adding \(1\) to \(A_x\) can be written as \(X \oplus A_x \oplus (A_x+1)\) using the value \(A_x\) before the addition. This differential update can be done fast, so it is fast enough as a whole. More generally, the value of \(f(A)\) after adding or subtracting any value from an element of \(A\) can also be computed fast.

Let us employ this observation to consider type-\(2\) queries as well.

Checking if \(A_i \geq 1\) for all \(N\) values will lead to TLE (Time Limit Exceeded). Instead, let us maintain the set of indices \(i\) such that \(A_i \geq 1\).

A type-\(1\) query keeps this set unchanged, or adds one element.

A type-\(2\) query subtracts \(1\) from \(A_i\) for each index \(i\) in this set, and reconstruct the new set (by removing those newly becoming \(A_i=0\)).

Since the values of \(A\) was all initially \(0\), the operations can be done in a total of \(O(N+Q)\) time.

The problem can be solved by appropriately implementing the idea above.

Sample code (Python 3)

input = __import__("sys").stdin.readline
n, q = map(int, input().split())
idxs = []
a = [0] * n
ans = 0
for _ in range(q):
    data = list(map(int, input().split()))
    if data[0] == 1:
        x = data[1] - 1
        if a[x] == 0:
            idxs.append(x)
        ans ^= a[x] ^ (a[x] + 1)
        a[x] += 1
    else:
        for v in idxs:
            ans ^= a[v] ^ (a[v] - 1)
            a[v] -= 1
        idxs = [v for v in idxs if a[v] != 0]
    print(ans)