题目背景

孙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$。