题目描述

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

给出 $Q$ 个询问，请按顺序处理。询问有两种，格式如下：

• 1 x：把 $A_x$ 的值增加 $1$；
• 2：对每个 $i = 1, 2, \ldots, N$，若 $A_i \ge 1$ 则把 $A_i$ 减少 $1$（等于 $0$ 的保持不变）。

请在处理完每个询问之后，输出 $A_1, A_2, \ldots, A_N$ 的按位异或（$\mathrm{XOR}$）值。

什么是按位异或？

非负整数 $A$ 与 $B$ 的按位异或 $A \oplus B$ 定义为：$A \oplus B$ 的二进制表示中 $2^k$ 位上的数字，当 $A$、$B$ 二进制表示中 $2^k$ 位的数字恰有一个是 $1$ 时为 $1$，否则为 $0$。

例如 $3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。多个数的异或与顺序无关。

输入格式

N Q
query_1
query_2
...
query_Q

其中每个询问是下面两种格式之一：

1 x

2

输出格式

输出 $Q$ 行，第 $i$ 行是处理完第 $i$ 个询问后所有元素的异或值。

输入示例 1

2 5
1 2
1 2
1 1
2
2

输出示例 1

1
2
3
1
0

示例 1 说明

• 第 $1$ 个询问后 $A = (0, 1)$，$0 \oplus 1 = 1$；
• 第 $2$ 个询问后 $A = (0, 2)$，$0 \oplus 2 = 2$；
• 第 $3$ 个询问后 $A = (1, 2)$，$1 \oplus 2 = 3$；
• 第 $4$ 个询问（类型 2）后 $A = (0, 1)$，异或为 $1$；
• 第 $5$ 个询问（类型 2）后 $A = (0, 0)$，异或为 $0$。注意第 $1$ 个元素已经是 $0$，不会变成 $-1$。

输入示例 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

示例 2 说明

第 $6$ 个询问是类型 $2$：此前 $A = (2, 2, 1)$，全部减 $1$ 后变成 $(1, 1, 0)$，异或为 $1 \oplus 1 \oplus 0 = 0$。

约束条件

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