Problem Description

给出一个长度为 $n$ 的数组 $a_0,\ldots,a_{n-1}$，有 $q$ 次操作，每次询问给出 $i, X$，你要求出$\sum_{j=0}^{X} a_{i \oplus j}$，其中 $\oplus$ 表示异或操作，特别的如果 $i \oplus j \geq n$，那么 $a_{i \oplus j} = 0$。支持单点修改。

Input

第一行给出 $n, q$。

第二行给出 $n$ 个数字 $a_0, ..., a_{n-1}$。

接下来 $q$ 行，每次输入一个 $op$ 表示操作序号。

若 $op=1$， 输入 $i, v$，表示将 $a_i$ 改成 $v$。

若 $op=2$，输入 $i, X$，表示查询 $\sum_{j=0}^{X} a_{i\oplus j}$。

#### 评测数据规模

$n, q \leq 524288,op \in \{1,2\},0 \leq i, X < n, 0 \leq v, a_i \leq 10^9$。

Output

对于每个 $op=2$ 输出答案。

#### 样例解释

$a_1+a_{1\oplus1}+\ldots+a_{1\oplus 5} + a_{1\oplus 6} = 1 + 1 + 5 + 4 + 4 + 1 + 0 = 16$.

第二次操作将 $a_1$ 改为 $4$，$a = \{1,4,4,5,1,4\}$.

$a_3+a_{3\oplus 1}+a_{3\oplus 2}+3_{3\oplus 3}=5+4+4+1=14$.

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

16
14