Given an array ~a~ of ~N~ integers, and ~Q~ queries, support the following operations:

• 1 i k Combine ~k~ consecutive elements beginning at index ~i~ (including the element at index ~i~) into one element in the current array. "Combining" means summing the values of the ~k~ elements into one.
• 2 i Uncombine the element at index ~i~ in the current array into its original elements in the original array.
• 3 i k Output the sum of ~k~ consecutive elements beginning at index ~i~ (including the element at index ~i~) in the current array.

~(1 \le k, i \le 10^5)~. Let ~M~ be the number of elements in the current array. Subtract ~M~ from ~i~ until ~i~ is in the range ~[1, M]~. Let ~L~ be the number of elements to the right of or at index ~i~ in the current array. Subtract ~L~ from ~k~ until ~k~ is in the range ~[1, L]~.

Input Specification

The first line will contain two integers, ~N, Q~ ~(1 \le N, Q \le 10^5)~.

The second line will contain ~N~ integers, the values of the original array ~(1 \le a_i \le 10^4)~.

The next ~Q~ lines will each contain a valid query as defined above.

Output Specification

For each type ~3~ query, output the answer on its own line.

Sample Input

3 9
1 3 4
1 1 2
3 1 1
3 1 2
2 1
3 2 2
3 2 1
1 2 2
1 1 2
3 10000 100000

Sample Output

4
8
7
3
8