# 3413. 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 \lt l,0 \leq Ai \leq 10^9$

### 输出格式

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

### 样例

Input
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

Output
15
12
11
15


### 提示

2 人解决，4 人已尝试。

3 份提交通过，共有 8 份提交。

9.0 EMB 奖励。