19068번 - Sequence 다국어

Yuta has an array $A_1$, $A_2$, $\ldots$, $A_n$ with $n$ integers, and he keeps a copy of the initial contents of array $A$ as $A'$ (initially, $A'_i = A_i$). Then he executes $m$ operations on the array $A$.

There are three types of operations:

• "1 $l$ $r$": Yuta wants to find the sum of $A_i$ for all $i$ in $[l, r]$.
• "2 $l$ $r$ $k$": Yuta runs the following pseudocode on the sequence $A$: for (int i = l; i <= r; i++) A[i] = A[i - k];
• "3 $l$ $r$": For all $i \in [l,r]$, Yuta changes $A_i$ back to $A'_i$.

Help Yuta execute all the given operations.

The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^5$).

The second line contains $n$ integers $A_i$ ($0 \leq A_i \leq 10^9$).

Then $m$ lines follow, each line describes an operation in the format shown above. It is guaranteed that $1 \le l \le r \le n$ and $1 \leq k < l$.

For each operation of the first type, print a single line with a single integer: the required sum.