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.