T426567 「YAC Round 5」异或操作真是太棒啦

 > 少女幻葬　～ Necro-Fantasy

八云蓝号称是幻想乡的数字的魔术师、最强式神、拥有验证哥德巴赫猜想程度的能力、拥有超越深蓝计算机程度的能力（笑）。最近她又感到无聊，毕竟三途河的宽度、~~八云紫的年龄~~ 也都已经算出来了，而且之前出的与 $\text{gcd}$ 和异或操作相关的那个题目 [八云蓝的 gcd 问题](https://www.luogu.com.cn/problem/T419838) 也被你做出来了。 所以这次八云蓝这次又来出题了，题目又和异或操作有关。 八云蓝给了你 $n$ 个数，$a_1, a_2, \ldots , a_n$ 。现在，八云蓝每次询问一个区间 $[l, r]$，对于这个区间你需要求出: $$ \bigoplus _{len=1}^{r - l + 1} \bigoplus _{i=l}^{r - len + 1} \text{xorsum}_{[i, i + len - 1]} $$ 其中 $\text{xorsum}_{[i, i + len - 1]} $ 表示区间 $[i, i + len - 1]$ 内元素的异或和。 ### 例如，对于区间 $[3, 5]$，那么你需要求出的是： $$ a_3 \oplus a_4 \oplus a_5 \oplus (a_3 \oplus a_4) \oplus (a_4 \oplus a_5) \oplus (a_3 \oplus a_4 \oplus a_5) $$ 其中 $\oplus$ 为 **按位异或** 运算。 同时，八云蓝还会动不动修改其中某一个数的值修改为 $x$（真是个让人为难的式神啊~）。

第一行输入两个正整数 $n,q$，分别表示 数的数量 和 操作次数。 接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots , a_n$。 接下来 $q$ 行，每行有三个数，有两种操作： - `1 k x` 为将某一个数修改为 $x$ 的操作。输入 $1$ 后，输入一个正整数 $k$ 与非负整数 $x$，表示将第 $k$ 个数字 $a_k$ 修改为 $x$。 - `2 l r` 为询问区间操作。输入 $2$ 后，输入两个正整数 $l,r$ ，表示询问这个区间对应的答案。

对于每次询问，输出一行一个非负整数，表示所求的答案。

#### 样例 1 解释 - 对于第一次询问，区间为 $[1, 3]$，此时的 $a_{[l,r]}=[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]$，此时的 $a_{[l,r]} = [3, 2, 3]$，故询问的结果是 $3\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0$ 。 #### 数据范围与约定： $1\le n,q\le 2\times 10^5$，$0\le a_i\le 10^9$ ， $1\le k\le n$，$0 \le x \le 10^9$, $1 \le l \le r \le n$ 。