绝世丑角

$$ \begin{array}{cr} \text{我好恨　恨这固执到厚颜无耻的人}\\ \text{竟和曾经快乐的我同个模样}\\ \text{即使信仰和记忆都}\overset{\text{Runtime Error}}{\text{遍体鳞伤}}\\ \text{仍在深渊妄想得到}\overset{\text{return }{\color{#EE0000}0}\text{;}}{{\color{#EE0000}\text{你}}\text{的回望}}\\ &\text{——《绝世丑角》} \end{array} $$  --- 在被修改的、破碎不堪的回忆中取出仅有的连续片段。 泠珞还是想知道，能否从中提取出，有意义的回忆呢。

对于两个非负整数 $a,b$，定义它们的 Nim 积为 $a\otimes b=\operatorname{mex}(\{(a\otimes d)\oplus(c\otimes b)\oplus (c\otimes d)|0\le c<a,0\le d<b\})$，其中 $x\oplus y$ 表示 $x$ 与 $y$ 的二进制异或和，$\operatorname{mex}(S)$ 表示**不存在**于 $S$ 中的最小的非负整数。 给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots,a_n$，给定 $q$ 次操作，每次操作有三个参数 $(t,\ell,r)$。 - 若 $t=1$，表示对于 $i=\ell,\ell+1,\cdots,r$，令 $a_i\gets a_i\otimes a_i$。 - 若 $t=2$，表示查询 $a_\ell\oplus a_{\ell+1}\oplus\cdots\oplus a_r$。 - 若 $t=3$，表示查询 $a_\ell+ a_{\ell+1}+\cdots+ a_r$。 你需要输出每次查询的结果。

第一行两个正整数 $n,q$。 接下来一行 $n$ 个非负整数，第 $i$ 个表示 $a_i$。 接下来 $q$ 行，每行三个正整数 $t,\ell,r$ 表示当前操作的参数。

对于每次查询操作，输出一行一个非负整数表示答案。

6 6
3 6 1 4 2 5
2 2 5
3 1 4
1 5 5
2 1 6
1 1 3
3 5 6

1
14
6
8

10 10
1234567890 130113 3614258193 1000000007 3146527164 3141592653 2147483648 998244353 2346886432 20151114
2 1 10
3 5 8
1 2 9
3 1 4
1 5 8
1 3 10
2 1 9
3 1 8
1 1 4
2 8 8

2499610911
9433847818
4602641167
4258698016
17656837678
704481058

10 10
36 14 35 0 13 0 11 3 5 20
2 1 10
3 1 4
2 2 5
3 1 8
3 1 4
2 5 6
2 8 9
3 3 7
3 1 10
2 1 5

29
85
32
112
85
13
6
59
137
4

10 10
36 14 35 0 13 0 11 3 5 20
1 1 10
2 1 4
1 2 5
2 1 8
2 1 4
2 5 6
2 8 9
1 3 7
1 1 10
2 1 5

12
21
22
14
5
9

10 10
36 14 35 0 13 0 11 3 5 20
1 5 5
3 1 4
2 2 5
3 1 8
1 9 9
2 5 6
1 9 9
3 3 7
3 1 10
2 1 5

85
39
109
10
56
133
3

10 10
36 14 35 0 13 0 11 3 5 20
1 1 10
3 1 4
2 2 5
3 1 8
1 1 10
2 5 6
1 1 10
3 3 7
3 1 10
2 1 5

112
52
139
14
76
179
7

10 10
36 14 35 0 13 0 11 3 5 20
1 3 8
1 1 6
1 2 10
3 1 4
2 2 5
3 1 8
2 5 6
3 3 7
3 1 10
2 1 5

119
61
139
8
73
176
15

**【样例 #1 解释】** 第一次操作是查询，输出 $6\oplus 1\oplus 4\oplus 2=1$。 第二次操作是查询，输出 $3+6+1+4=14$。 第三次操作是修改，序列变为 $[3,6,1,4,3,5]$。 第四次操作是查询，输出 $3\oplus6\oplus1\oplus4\oplus3\oplus5=6$。 第五次操作是修改，序列变为 $[2,5,1,4,3,5]$。 第六次操作是查询，输出 $3+5=8$。 **【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\le n\le2.5\times10^5$，$0\le a_i<2^{32}$，$1\le q\le 1\times10^5$，$1\le t\le 3$，$1\le \ell\le r\le n$。保证最后一次操作是查询操作。 | 子任务编号 | 分值 | $n\le $ | $q\le $ | $a_i<$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | $t\neq 1$ | | $2$ | $11$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | 若 $t=1$，则 $\ell=r$ | | $3$ | $19$ | $2.5\times10^5$ | $1\times10^5$ | $64$ | 无| | $4$ | $13$ | $1\times10^5$ | $3\times10^4$ | $2^{32}$ | $t\neq 3$ | | $5$ | $17$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | $t\neq 3$ | | $6$ | $7$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | 若 $t=1$，则 $\ell=1,r=n$ | | $7$ | $23$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | 所有 $t=1$ 的操作在 $t\neq 1$ 前 | | $8$ | $3$ | $1\times10^5$ | $3\times10^4$ | $2^{32}$ | 无 | | $9$ | $5$ | $2.5\times10^5$ | $1\times10^5$ | $2^{32}$ | 无 |