Description

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.

Input Format

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 Format

Output the result of each query.

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

7
25

Hint

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'<10^7$.
• For operations 1 and 2, $0\leq x \leq 20$ and $0 \le y < 2^x$.

Translated by ChatGPT 5