Rikka with Sequence

Problem Description

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:

Input

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$

Output

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

Sample 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

Sample Output

15
12
11
15

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6087