Rikka with Sequence

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has an array $A$ with $n$ numbers and he keeps a copy of the initial value of array $A$ as $A'(A'_i=A_i)$. Then he makes $m$ operations on it.

There are three types of operations:
$1\ l \ r$: Yuta wants Rikka to sum up $A_i$ for all $i$ in $[l,r]$.
$2 \ l\ r\ k$: Yuta runs the C++ code “for (int i=l;i<=r;i++) A[i]=A[i-k]” on sequence $A$. (The pascal version of the code snippet is “for i:=l to r do A[i]:=A[i-k]”).
$3\ l\ r$: Yuta changes $A_i$ back to $A'_i$, for all $i \in [l,r]$.

It is too difficult for Rikka. Can you help her?

The first line contains two numbers $1 \leq n,m \leq 2 \times 10^5$.

The second line contains n numbers $A_i$. Then m lines follow, each line describe an operation.

It is guaranteed that $1 \leq k<l, 0 \leq A_i \leq 10^9$

For each query, print a single line with a single number -- the answer.

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

15
12
11
15

2017 Multi-University Training Contest - Team 5