Janez 非常喜欢橙子！于是他制作了一台橙子扫描仪。通过摄像头和一台 Raspberry Pi 3b+ 计算机，他开始创建橙子的 3D 图像。他的图像处理器性能一般，因此他得到的唯一输出是一个 32 位整数，其中包含了橙皮上孔洞的信息。一个 32 位整数由 32 个数字（位）组成，每一位要么是 0，要么是 1。如果我们从 0 开始，通过为每一个等于 1 的第 $i$ 位加上 $2^i$ 即可得到 $D$。更正式地说，当 $D = d_{31} \cdot 2^{31} + d_{30} \cdot 2^{30} + \dots + d_1 \cdot 2^1 + d_0 \cdot 2^0$ 时，数字 $D$ 由序列 $d_{31}, d_{30}, \dots, d_0$ 表示。例如，13 表示为 $0, \dots, 0, 1, 1, 0, 1$。

Janez 扫描了 $n$ 个橙子；然而，有时他决定在程序执行期间重新扫描其中一个橙子（第 $i$ 个橙子）。这意味着从这次扫描开始，他将使用第 $i$ 个橙子的更新值。

Janez 想要分析这些橙子。他发现异或（XOR）运算非常有趣，因此他决定进行一些计算。他选择一个从 $l$ 到 $u$ 的橙子范围（其中 $l \le u$），并想要找出该范围内所有元素、该范围内所有连续元素对、所有连续元素序列，以此类推，直到包含 $u - l + 1$ 个连续元素（即范围内的所有元素）的序列的异或值。

即，如果 $l = 2$ 且 $u = 4$，并且存在扫描值数组 $A$，程序应返回 $a_2 \oplus a_3 \oplus a_4 \oplus (a_2 \oplus a_3) \oplus (a_3 \oplus a_4) \oplus (a_2 \oplus a_3 \oplus a_4)$ 的值，其中 $\oplus$ 表示异或运算，$a_i$ 表示数组 $A$ 中的第 $i$ 个元素。

异或运算定义如下： 如果第一个值的第 $i$ 位与第二个值的第 $i$ 位相同，则结果的第 $i$ 位为 0；如果第一个值的第 $i$ 位与第二个值的第 $i$ 位不同，则结果的第 $i$ 位为 1。

例如，$13 \oplus 23 = 26$。

输入格式

输入的第一行包含两个正整数 $n$ 和 $q$（动作的总数，包括重新扫描和查询）。

下一行包含 $n$ 个空格分隔的非负整数，代表数组 $A$ 的值（橙子的扫描结果）。元素 $a_i$ 包含第 $i$ 个橙子的值。索引 $i$ 从 1 开始。

接下来的 $q$ 行描述了动作，每行包含三个空格分隔的正整数。

如果动作类型为 1（重新扫描），第一个整数等于 1，后面跟着 $i$（Janez 想要重新扫描的橙子索引）和 $j$（第 $i$ 个橙子重新扫描的结果）。

如果动作类型为 2（查询），第一个整数等于 2，后面跟着 $l$ 和 $u$。

输出格式

对于每个查询，你应该打印一个整数作为该查询的匹配结果。每个值应打印在新的一行中。注意，第 $i$ 行的输出应与第 $i$ 个查询的结果相匹配。

数据范围

• $a_i \le 10^9$
• $0 < n, q \le 2 \cdot 10^5$

子任务

1. [12 分]: $0 < n, q \le 100$
2. [18 分]: $0 < n, q \le 500$，且没有重新扫描（类型 1 的动作）
3. [25 分]: $0 < n, q \le 5000$
4. [20 分]: $0 < n, q \le 2 \cdot 10^5$，且没有重新扫描（类型 1 的动作）
5. [25 分]: 无附加限制。

样例

样例输入 1

3 3
1 2 3
2 1 3
1 1 3
2 1 3

样例输出 1

2
0

说明 1

最初，$A = [1, 2, 3]$。第一个查询是在全范围上进行的。分析结果为 $1 \oplus 2 \oplus 3 \oplus (1 \oplus 2) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 2$。

然后第一个橙子的值更新为 3。这导致同一查询（在范围 $[1, 3]$ 上）的结果变为 $3 \oplus 2 \oplus 3 \oplus (3 \oplus 2) \oplus (2 \oplus 3) \oplus (3 \oplus 2 \oplus 3) = 0$。

样例输入 2

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

样例输出 2

2
5
4
4