Sereja and Array

Sereja has got an array, consisting of $n$ integers $a_1,a_2,...,a_n$. Sereja is an active boy, so he is now going to complete $m$ operations. Each operation will have one of the three forms:

• Make $v_i$-th array element equal to $x_i$. In other words, perform the assignment $a_{v_i}=x_i$.

• Increase each array element by $y_i$. In other words, perform $n$ assignments $a_i=a_i+y_i(1\le i\le n)$.

• Take a piece of paper and write out the $q_i$-th array element. That is, the element $a_{q_i}$.

Help Sereja, complete all his operations.

Input

The first line contains integers $n,m(1\le n,m\le 10^5)$. The second line contains $n$ integers $a_1,a_2,...,a_n(1\le a_i\le 10^9)$ — the original array.

Next $m$ lines describe operations, the $i$-th line describes the $i$-th operation. The first number in the $i$-th line is integer $t_i(1\le t_i\le 3)$, that represents the operation type.

• If $t_i=1$, then it is followed by two integers $v_i$ and $x_i(1\le v_i\le n,1\le x_i\le 10^9)$.

• If $t_i=2$, then it is followed by integer $y_i(1\le y_i\le 10^4)$.

• If $t_i=3$, then it is followed by integer $q_i(1\le q_i\le n)$.

Output

For each third type operation print value $a_{q_i}$. Print the values in the order, in which the corresponding queries follow in the input.

Examples