There are $N$ piles of sand in a line. The $i$th pile from the left initially has $s_i$ units of sand. Answer $Q$ queries, the $i$th query contains $3$ integers $a_i$, $b_i$, and $c_i$:

If $a_i$ is 1: move $c_i$ units of sand from the $b_i$th pile to the ($b_i-1$)th pile. ($2\le b_i\le N$).

If $a_i$ is 2: move $c_i$ units of sand from the $b_i$th pile to the ($b_i+1$)th pile. ($1\le b_i\le N-1$).

If $a_i$ is 3: find the total units of sand in all of the piles between pile $b_i$ and $c_i$, inclusive. ($1\le b_i\le c_i\le N$).

The queries will never make you remove more sand from a pile than it contains, or move a negative amount of sand.

Constraints

$1\le N,Q\le {10}^6$

$1\le s_i\le {10}^3$

Subtask 1 [40%]

All queries will have $a_i$ = $3$.

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains $2$ space-separated integers, $N$ and $Q$.

The second line contains $N$ space-separated integers, the $i$th integer representing the units of sand in the $i$th pile.

The next $Q$ lines each contain $3$ space-separated integers: $a_i$, $b_i$, and $c_i$.

Output Specification

For each query with $a_i=3$, output a line containing a single integer: the total units of sand in all of the piles between pile $b_i$ and $c_i$, inclusive.

Sample Input

5 6
4 2 10 3 4
3 2 4
1 2 2
2 3 8
3 1 3
2 1 4
3 2 5

Sample Output

15
8
21

Explanation for Sample

The piles are initially $[4,2,10,3,4]$.

After the $2$nd query they are $[6,0,10,3,4]$.

After the $3$rd query they are $[6,0,2,11,4]$.

After the $5$th query they are $[2,4,2,11,4]$.