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 \leq b_i \leq 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 \leq b_i \leq 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 \leq b_i \leq c_i \leq 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 \leq N, Q \leq 10^6~

~1 \leq s_i \leq 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]~.