Background

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.

Problem 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