P6587 Chaochao’s Sequence (Enhanced)

Sun 1chao always likes to talk nonsense. One day, he casually said a sequence, and then wanted to modify and sum the values at some specific positions. Since Sun 1chao is very weak, he came to you for help. ## Please do not copy solutions.

Given a sequence $a$, and two types of operations: - `1 x y v`: add $v$ to all $a_i$ where $i\equiv y\pmod {2^x}$. - `2 x y`: query the sum of all $a_i$ where $i\equiv y\pmod {2^x}$. **This problem is strictly online.**

The first line contains two integers $n,m$. The second line contains $n$ integers; the $i$-th one is $a_i$. Then follow several lines, each containing several integers: When $op=1$, the last three integers of $op'$ are, in order, $x,y,v$ for this operation; When $op=2$, the last two integers of $op'$ are, in order, $x,y$ for this operation. It is guaranteed that there are no extra integers in the input. For each operation, $op=(\operatorname{lastans}+op')\bmod 2+1$. Here $\rm lastans$ denotes the answer output by the previous query; if there has been no query before, then $\rm lastans=0$.

Output the result of each query.

#### Sample Explanation For Sample 1: - For the first operation, $op=2$, the contributing indices $i$ are $1,5$, so the answer is $7$. - For the second operation, $op=1$, the indices $i$ that need to add $3$ are $1,3,5$, so add $3$ to $a_1,a_3,a_5$. - For the third operation, $op=2$, the contributing indices $i$ are $1,2,3,4,5$, so the answer is $25$. #### Constraints - For $10\%$ of the testdata, $1\le n,m \leq 10^3$. - For $70\%$ of the testdata, there is a newline after each operation. - For $100\%$ of the testdata, $1\le n,m \leq 2\times10^5$, $0 \leq a_i,y,v,op'