Problem Statement

There is a length-$N$ integer sequence $A=(A_1,A_2,\ldots,A_N)$. Initially, all elements of $A$ are $0$.

You will be given $Q$ queries, which should be processed in order. There are two types of queries, each given in one of the following formats:

• 1 x: Increase the value of $A_x$ by $1$.
• 2: For each $i=1,2,\ldots,N$, if $A_i \geq 1$, decrease the value of $A_i$ by $1$.

Find the bitwise $\mathrm{XOR}$ of $A_1,A_2,\ldots,A_N$ immediately after processing each query.

What is bitwise $\mathrm{XOR}$?

The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, denoted $A \oplus B$, is defined as follows:

• In the binary representation of $A \oplus B$, the digit in the $2^k$ ($k \geq 0$) place is $1$ if exactly one of the digits in the $2^k$ place of $A$ and $B$ in their binary representations is $1$, and $0$ otherwise.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
More generally, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this value does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

Constraints

• $1\le N\le 5\times 10^5$
• $1\le Q\le 5\times 10^5$
• $1\le x\le N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

Each query is given in one of the following $2$ formats:

$1$ $x$

$2$

Output

Output $Q$ lines.

The $i$-th line $(1\le i\le Q)$ should contain the bitwise $\mathrm{XOR}$ of $A_1,A_2,\ldots,A_N$ for $A$ immediately after processing the $i$-th query.

2 5
1 2
1 2
1 1
2
2

1
2
3
1
0

After processing the first query, $A=(0,1)$. The bitwise $\mathrm{XOR}$ of $0,1$ is $1$, so output $1$ on the first line.

After processing the second query, $A=(0,2)$. The bitwise $\mathrm{XOR}$ of $0,2$ is $2$, so output $2$ on the second line.

After processing the third query, $A=(1,2)$. The bitwise $\mathrm{XOR}$ of $1,2$ is $3$, so output $3$ on the third line.

After processing the fourth query, $A=(0,1)$. The bitwise $\mathrm{XOR}$ of $0,1$ is $1$, so output $1$ on the fourth line.

After processing the fifth query, $A=(0,0)$. The bitwise $\mathrm{XOR}$ of $0,0$ is $0$, so output $0$ on the fifth line.

3 8
1 2
1 3
1 1
1 2
1 1
2
1 3
1 1

1
0
1
2
1
0
1
2

• 来源：AtCoder ABC 470 C