「SMOI-R1」Apple

**为了卡掉错误算法，我们把时限改为 680ms。**

LAR 有 $2^n$ 个苹果，苹果用 $0$ 到 $2^n - 1$ 编号，编号为 $i$ 的苹果的价值是 $v_i$。 如果 $A\operatorname{or}B=A$，那么可以说 $A$ 包含 $B$（$\operatorname{or}$ 是按位或）。 因为 LAR 的苹果太多了，所以他不知道如何挑选苹果。他想进行一些操作，方便他吃苹果。 总共有两种操作，共 $q$ 个操作： - $1\ S$ ，询问所有编号被 $S$ 包含的苹果的价值总和。 - $2\ S\ A$ ，改变编号为 $S$ 的苹果的价值为 $A$（将 $v_S$ 改为 $A$）。

第一行有两个整数 $n$ 和 $q$。$q$ 代表操作次数。 第二行有 $2^n$ 个数，第 $i$ 个数代表 $v_{i-1}$ 的值。 接下来有 $q$ 行，每行代表 LAR 要进行的一个操作，详细见上文。

对于每个操作 $1$，输出一个数，代表这个询问的答案。

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

4
7
10

### 样例解释 初始时 $v=[1,2,3,2]$。 第一个操作时询问所有编号被 $2$ 包含的苹果的价值总和。被 $2$ 包含的数为 $0,2$，所以答案为 $v_0 + v_2=4$。 第二个操作是把 $v_0$ 改为 $4$，此时 $v=[4,2,3,2]$。 第三个操作时询问所有编号被 $2$ 包含的苹果的价值总和。被 $2$ 包含的数为 $0,2$，所以答案为 $v_0 + v_2=7$。 第四个操作是把 $v_3$ 改为 $1$，此时 $v=[4,2,3,1]$。 第五个操作时询问所有编号被 $3$ 包含的苹果的价值总和。被 $3$ 包含的数为 $0,1,2,3$，所以答案为 $v_0 + v_1 + v_2 + v_3=10$。 ### 数据范围 **本题采用捆绑测试**。 subtask 编号|$n\leq$|$q\leq$|特殊性质|分值 -|-|-|-|- $1$|$10$|$10^4$|无|$10$ $2$|$16$|$3\times 10^5$|无|$20$ $3$|$20$|$3\times10^5$|只有操作 1|$10$ $4$|$20$|$10^5$|无|$20$ $5$|$20$|$3\times10^5$|无|$40$ 对于 $100\%$ 的数据，保证 $1\le n \leq 20$ ，$1 \le q\leq3\times10^5$，$0\leq v_i\leq 2^{31}-1$ 。 **提示**：本题输入量较大，请使用快读。请注意代码**常数**。