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$）。
## Input
第一行有两个整数 $n$ 和 $q$。$q$ 代表操作次数。
第二行有 $2^n$ 个数，第 $i$ 个数代表 $v_{i-1}$ 的值。
接下来有 $q$ 行，每行代表 LAR 要进行的一个操作，详细见上文。
## Output
对于每个操作 $1$，输出一个数，代表这个询问的答案。
[samples]
## Background
**为了卡掉错误算法，我们把时限改为 680ms。**
## Note
### 样例解释
初始时 $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$ 。
**提示**：本题输入量较大，请使用快读。请注意代码**常数**。