问题陈述

有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。最初， $A$ 的所有元素都是 $0$ 。

您将收到 $Q$ 个查询，这些查询应按顺序处理。查询有两种类型，每种都以下列格式之一给出：

• 1 x :将 $A_x$ 的值增加 $1$ 。
• 2 :对于每个 $i=1,2,\ldots,N$ 如果是 $A_i \geq 1$ ，则将 $A_i$ 的值减少 $1$ 。

在处理完每个查询后，立即查找 $A_1,A_2,\ldots,A_N$ 的位 $\mathrm{XOR}$ 。

什么是位向 $\mathrm{XOR}$ ？

非负整数 $A$ 和 $B$ 的位向 $\mathrm{XOR}$ 表示为 $A \oplus B$ ，其定义如下：

• 在 $A \oplus B$ 的二进制表示中，如果 $A$ 和 $B$ 的二进制表示中 $2^k$ 位的数字中正好有一位是 $1$ ，则 $2^k$ （ $k \geq 0$ ）位的数字是 $1$ ，否则是 $0$ 。

例如， $3 \oplus 5 = 6$ （二进制： $011 \oplus 101 = 110$ ）。
更一般地说， $k$ 非负整数 $p_1, p_2, p_3, \dots, p_k$ 的比特 $\mathrm{XOR}$ 定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ ，可以证明这个值与 $p_1, p_2, p_3, \dots, p_k$ 的阶数无关。

约束条件

• $1\le N\le 5\times 10^5$
• $1\le Q\le 5\times 10^5$
• $1\le x\le N$
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

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

每个查询以下列 $2$ 格式之一给出：

$1$ $x$

$2$

输出

输出 $Q$ 行。

在处理完 $i$ }-th 查询后， $i$ -行 $(1\le i\le Q)$ 应该立即包含 $A_1,A_2,\ldots,A_N$ for $A$ 的比特 $\mathrm{XOR}$ 。

输入示例 1

2 5
1 2
1 2
1 1
2
2

样本输出 1

1
2
3
1
0

处理完第一个查询后，输出 $A=(0,1)$ 。 $0,1$ 的比特 $\mathrm{XOR}$ 为 $1$ ，因此在第一行输出 $1$ 。

处理第二个查询后， $A=(0,2)$ 。 $0,2$ 的位向 $\mathrm{XOR}$ 为 $2$ ，因此在第二行输出 $2$ 。

处理完第三个查询后， $A=(1,2)$ 。 $1,2$ 的位向 $\mathrm{XOR}$ 为 $3$ ，因此在第三行输出 $3$ 。

处理完第四个查询后， $A=(0,1)$ 。 $0,1$ 的比特 $\mathrm{XOR}$ 为 $1$ ，因此在第四行输出 $1$ 。

处理完第五个查询后， $A=(0,0)$ 。 $0,0$ 的比特 $\mathrm{XOR}$ 为 $0$ ，因此在第五行输出 $0$ 。

输入示例 2

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

输出样本 2

1
0
1
2
1
0
1
2