题目描述

给你一个初始长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，接下来有 $q$ 次操作，操作分为如下三种类型：

• 1 x：在数列 $a$ 的末尾加入一个数值为 $x$ 的元素（即：令 $n$ 增加 $1$，然后令 $a_n = x$）
• 2：将数列 $a$ 中每个元素的数值都增加 $1$；
• 3：求数列 $a$ 中所有元素的异或和（即求：$a_1 \oplus a_2 \oplus \ldots \oplus a_n$，这里 $\oplus$ 是异或符号）。

对于每次 3 操作，要求输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $q$，以空格分隔，分别表示初始数列 $a$ 的长度以及操作次数。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

接下来 $q$ 行，每行包含一个操作，形如 1 x 或 2 或 3。

输出格式

对于每次 3 操作，输出一行，包含一个整数，表示数列 $a$ 中所有元素的异或和。

样例

3 5
1 2 3
3
1 5
3
2
3

0
5
3

12 10
100 20 17 85 99 62 37 58 3 108 120 55
1 7
3
2
3
1 15
1 78
2
3
1 130
3

81
82
116
246

说明/提示

样例 1 解释

初始的序列为 $[ 1, 2, 3 ]$。

第 $1$ 次操作为询问异或和，数列中所有元素的异或和为 $1 \oplus 2 \oplus 3 = 0$。

第 $2$ 次操作为加入一个数值为 $5$ 的元素，此时数列变为 $[1, 2, 3, 5]$。

第 $3$ 次操作为询问异或和，数列中所有元素的异或和为 $1 \oplus 2 \oplus 3 \oplus 5 = 5$。

第 $4$ 次操作为将数列中的每个元素的数值 $+1$，操作后数列变为 $[ 2, 3, 4, 6 ]$。

第 $5$ 次操作为询问异或和，数列中所有元素的异或和为 $2 \oplus 3 \oplus 4 \oplus 6 = 3$。

数据规模与约定

• 对于 $20\%$ 的数据，$n, q, a_i, x \le 100$
• 对于 $50\%$ 的数据，$n, q \le 1000, a_i, x \lt 2^{10}$
• 对于 $100\%$ 的数据，$1 \le n, q \le 10^5$，$0 \le a_i, x \lt 2^{20}$