问题描述

我们有一个长度为 $N$ 的整数序列 $A$。
你将在这个序列上处理 $Q$ 个查询。在第 $i$ 个查询中，给定值 $T_i$，$X_i$ 和 $Y_i$，请执行以下操作：

• 如果 $T_i = 1$，将 $A_{X_i}$ 替换为 $A_{X_i} \\oplus Y_i$。
• 如果 $T_i = 2$，打印 $A_{X_i} \\oplus A_{X_i + 1} \\oplus A_{X_i + 2} \\oplus \\dots \\oplus A_{Y_i}$。

这里，$a \\oplus b$ 表示 $a$ 和 $b$ 的按位异或。

什么是按位异或？

整数 $A$ 和 $B$ 的按位异或 $A \\oplus B$ 定义如下：

• 当把 $A \\oplus B$ 用二进制表示时，在第 $2^k$ 位上（$k \\geq 0$）的数字为 $1$，当且仅当 $A$ 或 $B$ 中有且仅有一个数字在第 $2^k$ 位上为 $1$，否则为 $0$。

例如，$3 \\oplus 5 = 6$。（二进制表示为：$011 \\oplus 101 = 110$。）

约束条件

• $1 \le N \le 300000$
• $1 \le Q \le 300000$
• $0 \le A_i \lt 2^{30}$
• $T_i$ 取值为 $1$ 或 $2$。
• 如果 $T_i = 1$，则 $1 \le X_i \le N$，并且 $0 \le Y_i \lt 2^{30}$。
• 如果 $T_i = 2$，则 $1 \le X_i \le Y_i \le N$。
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $Q$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ $T_1$ $X_1$ $Y_1$ $T_2$ $X_2$ $Y_2$ $T_3$ $X_3$ $Y_3$ $\hspace{22pt} \vdots$ $T_Q$ $X_Q$ $Y_Q$

输出

对于每个查询中的 $T_i = 2$，按接收顺序逐行打印结果。

示例输入 1

3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3

示例输出 1

0
1
2

在第一个查询中，我们打印 $1 \\oplus 2 \\oplus 3 = 0$。
在第二个查询中，我们打印 $2 \\oplus 3 = 1$。
在第三个查询中，我们用 $2 \\oplus 3 = 1$ 替换了 $A_2$。
在第四个查询中，我们打印 $1 \\oplus 3 = 2$。

示例输入 2

10 10
0 5 3 4 7 0 0 0 1 0
1 10 7
2 8 9
2 3 6
2 1 6
2 1 10
1 9 4
1 6 1
1 6 3
1 1 7
2 3 5

示例输出 2

1
0
5
3
0