题目描述

这是一道模板题。

坎格鲁斯普雷给了你一个长度为 $n$ 的序列 $a_i$ ，你要支持以下操作：

1、给序列中的某个元素加上 $x$ ；

2、查询序列中 $[l,r]$ 元素的异或和。

显然，这是一道树状数组的模板题，坎格鲁斯普雷相信你很快能秒了他。

输入格式

输入第一行两个整数 $n$ , $q$ ,分别表示序列长度和操作数量。 $(1 \leq n,q \leq 2 \times 10^5)$

输入第二行 $n$ 个整数 $a_i$ ，表示一开始的序列。 $(1 \leq a_i \leq 10^5)$

之后 $q$ 行，每行先一个整数 $op$ ，表示操作类型。若 $op=1$ ，则接下来两个整数 $p$ , $x$ ,表示让下标为 $p$ 的数加上 $x$ ;若 $op=2$ ，则接下来两个整数 $l$ , $r$ ,表示查询序列中 $[l,r]$ 元素的异或和。 $(op \in \{1,2\},1 \leq p,l,r \leq n,1 \leq x \leq 10^5,l \leq r)$

输出格式

对于每个 $op=2$ 的操作，输出一行一个整数表示答案。

输入输出样例

输入 #1

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

输出 #1

0
4

说明与提示

对于样例 #1:

一开始序列为 $[1,2,3,4,5]$ 。

对于操作 $1$ : 答案为 $1\ xor\ 2\ xor\ 3=0$ 。

操作 $2$ , $3$ 进行完成后，序列为 $[3,2,7,4,5]$ 。

对于操作 $4$ : 答案为 $2\ xor\ 7\ xor\ 4\ xor\ 5=4$ 。