题目背景

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

天空中，点点滴滴的光芒融合在一起，清澈而宁静。眼前的风景是那么熟悉又陌生。

“我们再待一会儿如何，就像以前一样......”
“和你，和小镇，和星空......”

题目描述

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

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