Joe is an economical man and he has found a new scheme to save some money! Joe wants to save money on his water bill, so he decides to collect rainwater. Joe has a row of $N$ water containers, all initially empty and each with a maximum capacity of $v_i$ liters of water. The containers are connected in such a way that when container $i$ overflows, the excess liquid flows to container $i+1$. When container $N$ overflows, the extra water magically disappears. Joe wishes to gather information about the efficacy of his setup, and so he has prepared $Q$ queries of the following types:

• $1lrv$ : Rainfall arrives, and $v$ liters of water falls directly into each container from position $l$ to $r$ inclusive.
• $2xv$ : Joe changes the maximum capacity of bucket $x$ to $v$. If the volume decreases, any resulting overflow passes on to bucket $x+1$ as usual.
• $3x$ : Joe wishes to know the current volume of water being held in container $x$.

Constraints

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

$1\le x_i\le N$

$1\le l_i\le r_i\le N$

$1\le v_i\le {10}^{12}$

Subtask 1 [10%]

$1\le N,Q\le 100$

Subtask 2 [10%]

All queries of type $3$ appear after all queries of type $1$; there are no queries of type $2$.

Subtask 3 [30%]

For all queries of type $1$, $l_i=r_i$.

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line will contain $N$ and $Q$, the number of containers and number of queries respectively.

The second line will contain $N$ space-separated integers, $v_1,v_2,\dots ,v_N$.

The next $Q$ lines will contain queries of the form mentioned in the problem description.

Output Specification

Output the answer to each type $3$ query on separate lines.

Sample Input

5 5
4 5 2 9 3
1 1 2 3
2 1 1
1 2 5 2
3 4
3 5

Sample Output

4
2