题目背景

$$\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$				若 $t=1$，则 $\ell=r$
$3$	$19$			$64$	无
$4$	$13$	$1\times10^5$	$3\times10^4$	$2^{32}$	$t\neq 3$
$5$	$17$	$2.5\times10^5$	$1\times10^5$
$6$	$7$				若 $t=1$，则 $\ell=1,r=n$
$7$	$23$				所有 $t=1$ 的操作在 $t\neq 1$ 前
$8$	$3$	$1\times10^5$	$3\times10^4$		无
$9$	$5$	$2.5\times10^5$	$1\times10^5$