[SBCOI2020] 归家之路

时光流逝，岁月无痕。 小镇的夜空中，缀满了无数宝石一般的闪烁星辰。 依旧是那片星空，依旧是那个小镇。 ...... “好久不见啊。” “不知不觉，竟然已经过去了那么久了...” “但是，这座小镇还是曾经的那个小镇啊。” “只不过，我们都不再是过去的自己了呢。” “你还记得吗，我们曾经一起在这里看雪，一起玩游戏...” “可是游戏结局明明一开始就已经决定了...真是太坏了...” “嘿嘿，说起来你还从来没赢我过呢......” “我还记得，你以前说过，每当世界上有一份思念，便会化成一片雪花在这里飘落...” “嗯，我只要看着冬天的雪便能想起你了。我知道，这一定是你的思念吧...” “我也看到了，如同雪花般飘落的记忆......” 天空中，点点滴滴的光芒融合在一起，清澈而宁静。眼前的风景是那么熟悉又陌生。  “我们再待一会儿如何，就像以前一样......” “和你，和小镇，和星空......”

天空中一共有 $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}$ 取模。

第一行两个整数 $n,q$。 第二行 $2^n$ 个整数，用空格隔开，表示 $a_0,a_1,\cdots,a_{2^n-1}$。 接下来 $q$ 行，每行代表一个操作，格式见【题目描述】。

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

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

36
22

**【样例解释】** 第一次是询问，$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`。 ~~也就是【直接自然溢出啥事没有】。~~