题目背景

为了卡掉错误算法，我们把时限改为 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$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，保证 $1\le n \leq 20$ ，$1 \le q\leq3\times10^5$，$0\leq v_i\leq 2^{31}-1$ 。

提示：本题输入量较大，请使用快读。请注意代码常数。