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:

1. Make $*v*_{*i*}$-th array element equal to $*x*_{*i*}$. In other words, perform the assignment $*a*_{*v*_{*i*}} = *x*_{*i*}$.
2. Increase each array element by $*y*_{*i*}$. In other words, perform $*n*$ assignments $*a*_{*i*} = *a*_{*i*} + *y*_{*i*}$ $(1 ≤ *i* ≤ *n*)$.
3. 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 ≤ *n*, *m* ≤ 10^{5})$. The second line contains $*n*$ space-separated integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(1 ≤ *a*_{*i*} ≤ 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 ≤ *t*_{*i*} ≤ 3)$ that represents the operation type. If $*t*_{*i*} = 1$, then it is followed by two integers $*v*_{*i*}$ and $*x*_{*i*}$, $(1 ≤ *v*_{*i*} ≤ *n*, 1 ≤ *x*_{*i*} ≤ 10^{9})$. If $*t*_{*i*} = 2$, then it is followed by integer $*y*_{*i*}$ $(1 ≤ *y*_{*i*} ≤ 10^{4})$. And if $*t*_{*i*} = 3$, then it is followed by integer $*q*_{*i*}$ $(1 ≤ *q*_{*i*} ≤ *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.