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.

제한

힌트