题目描述

有一个长度为 $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$ 的二进制表示中，$2^k$（$k \geq 0$）位上的数字为 $1$，当且仅当 $A$ 与 $B$ 的二进制表示中 $2^k$ 位上的数字恰好有一个为 $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$ 行 $(1\le i\le Q)$ 输出处理完第 $i$ 个查询后 $A_1,A_2,\ldots,A_N$ 的按位 $\mathrm{XOR}$。

2 5
1 2
1 2
1 1
2
2

1
2
3
1
0

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

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

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

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

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

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

子任务设置

• 子任务 1（90 分）：$N,Q \le 2000$。
• 子任务 2（210 分）：无特殊限制。