시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 512 MB 1 1 1 100.000%

문제

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.

예제 입력 1

5 7
1 2 3 4 5
1 1 5
2 3 4 1
1 1 5
2 3 4 2
1 1 5
3 1 5
1 1 5

예제 출력 1

15
12
11
15