Description

天空中一共有 $2^n$ 颗星，依次编号为 $0,1,...,2^n-1$。每颗星都有一个亮度值。初始时第 $i$ 颗星的亮度值为 $a_i$。

对于两个正整数 $a,b$ 我们定义一种布尔类型运算 $a\otimes b$ 。如果在 $a$ 的二进制表示中，满足每一个 $a$ 是 $1$ 的位，$b$ 的对应位也是 $1$，那么 $a\otimes b$ 为 True , 否则 $a\otimes b$ 为 False。
若两数在二进制表示下的位数不同，则将两数 右对齐 后在左侧补0。例如两个数是 $1$ 和 $11$ （二进制），$1$ 会变成 $01$。

对于这些星的亮度值有两种操作：

第一种：$1$ $a$ $b$ $k$。对于所有的满足 $a\otimes c$ 值为 True 以及 $c\otimes b$ 值为 True 的 $c$，将第 $c$ 颗星的亮度值加上 $k$。

第二种：$2$ $a$ $b$。若第 $c$ 颗星的编号 $c$ 满足 $a\otimes c$ 值为 True 以及 $c\otimes b$ 值为 True。求出所有第 $c$ 颗星的亮度总和，答案对 $2^{32}$ 取模。

Input Format

第一行两个整数 $n,q$。

第二行 $2^n$ 个整数，用空格隔开，表示 $a_0,a_1,\cdots,a_{2^n-1}$。

接下来 $q$ 行，每行代表一个操作，格式见【题目描述】。

Output Format

对于每一个 $2$ 操作，输出一行表示答案。

3 3
1 2 3 4 5 6 7 8
2 0 7
1 1 5 1
2 1 7

36
22

Hint

【样例解释】

第一次是询问，$0$ 的二进制表示为 $000$， $7$ 的二进制表示为 $111$ 。此时，所有数都满足，即求的是所有数之和，为 $36$。

第二次是修改，$1$ 的二进制表示为 $001$，$5$ 的二进制表示为 $101$，发现 $c=1,5$ 满足，二进制表示分别为 $001$，$101$所以 $a_1,a_5$ 的值从 $2,6$ 变为 $3,7$。

第三次是询问，$1$ 的二进制表示为 $001$，$7$ 的二进制表示为 $111$，发现 $c=1,3,5,7$ 满足，二进制表示分别为 $001$，$011$，$101$，$111$。求的是 $a_1,a_3,a_5,a_7$ 的和 $3+4+7+8=22$。

【数据范围】

本题捆绑测试，共有 $4$ 个子任务。

$Subtask 1(1\%)$：答案为样例。

$Subtask 2(9\%)$：$n \le 12,m \le 2\times 10^3$。

$Subtask 3(15\%)$：所有 $2$ 操作都在 $1$ 操作之后。

$Subtask 4(75\%)$：没有任何额外限制。

对于 $100\%$ 的数据，$1 \le n \le 16,1 \le m \le 2\times 10^5, 0 \le a,b \le 2^n-1,0 \le a_i,k \le 2^{32}-1$。

【温馨提示】

对 $2^{32}$ 取模，可以直接用无符号 32 位整形的数据类型进行运算。在 c++ 中就是 unsigned int。

也就是【直接自然溢出啥事没有】。