题目描述

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

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

数据保证：每次执行 3 操作前数列中所有元素的均大于 $0$。

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

输入格式

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

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

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

输出格式

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

样例

3 5
1 2 3
4
1 5
4
2
4

0
5
3

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

81
82
18
144

说明/提示

样例 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$ 均 $\ge 1$，$a_i, x$ 均 $\ge 0$。