超超的序列 加强

孙1超总是喜欢疯言疯语，有一天，他随口说出了一串序列，又想对某几个特定位置的值进行修改和求和。由于孙1超十分菜，所以他来找你帮助。 ## 请不要抄题解。

给定序列 $a$，并且给出两种操作： - `1 x y v`：将所有 $a_i$ 的值加上 $v$，其中 $i\equiv y\pmod {2^x}$。 - `2 x y`：询问所有 $a_i$ 的和，其中 $i\equiv y\pmod {2^ x}$。 **本题强制在线。**

第一行 $n,m$ 两个整数。 第二行 $n$ 个整数，第 $i$ 个表示 $a_i$。 接下来若干行，每行给出若干个整数： 当 $op=1$ 时，$op'$ 的后三个整数依次为该操作的 $x,y,v$； 当 $op=2$ 时，$op'$ 的后两个个整数依次为该操作的 $x,y$。 其中保证没有多余的数输入。 每次操作的 $op=(\operatorname{lastans}+op')\bmod 2+1$。 其中 $\rm lastans$ 表示上一个输出的答案，若之前没有询问，则 $\rm lastans=0$。

输出每次询问的结果。

5 3
1 2 3 4 6
1 2 1
1 1 1 3
2 0 0

7
25

#### 样例解释 对于样例 1： - 第一个操作 $op=2$，需要计算贡献的 $i$ 为 $1,5$，答案为 $7$。 - 第二个操作 $op=1$， 需要加上 $3$ 的 $i$ 为 $1,3,5$，将 $a_1,a_3,a_5$ 加上 $3$。 - 第三个操作 $op=2$， 需要计算贡献的 $i$ 为 $1,2,3,4,5$，答案为 $25$。 #### 数据范围 - 对于 $10\%$ 的数据，$1\le n,m \leq 10^3$。 - 对于 $70\%$ 的数据，每一个操作后面有一个换行。 - 对于 $100\%$ 的数据，$1\le n,m \leq 2\times10^5$，$0 \leq a_i,y,v,op'<10^7$。 - 对于操作 1 和 2，$0\leq x \leq 20$ 且 $0 \le y < 2^x$。