In the city where Hyunbin lives, a concert is held every day.

Hyunbin hates loud noises, so he installed $N$ noise barriers, which are sequentially numbered from $1$ to $N$. The $i$-th noise barrier can absorb $D_i$ units of noise. After installing the noise barriers, he made a rule that all future concerts can only be held between two neighboring noise barriers. In other words, all future concerts can only be held between noise barrier $c$ and noise barrier $c+1$ for some integer $c$. ($1 \leq c < N$)

Unlike Hyunbin's plan to absorb all the noise and enjoy the quiet days, sometimes noise barriers were unable to withstand the whole noise from a concert. Suppose a concert is held between noise barriers $c$ and $c+1$, and emits $x$ units of noise. Noise barrier $c$ only absorbs $\min(D_c, x)$ units of noise, and if there is some noise left unabsorbed, it is spread to barrier $c-1$. Likewise, noise barrier $c+1$ only absorbs $\min(D_{c+1}, x)$ units of noise, and the rest of the noise spreads to barrier $c+2$. This procedure is repeated until there is no noise left, or some noise is unabsorbed, but there is no noise barrier to absorb it.

After each concert, Hyunbin has decided to enhance each of the $N$ noise barriers' absorption capacity by the amount of noise it has absorbed. Thus, if the noise barrier $k$ has absorbed $x$ units of noise, its absorption capacity becomes $D_k+x$ right after the concert.

Hyunbin performs one of the two following operations $Q$ times.

• $1$ $c$ $x$: A concert which emits $x$ units of noise is held between noise barriers $c$ and $c+1$, and after that, the noise barriers are enhanced subsequently. ($1\leq c
• $2$ $c$: Hyunbin measures the absorption capacity of barrier $c$. ($1\leq c \leq N$)

Print the absorption capacity of the noise barrier each time an operation of type $2$ is performed.

Input

The first line of input contains an integer $N$, denoting the number of noise barriers Hyunbin has installed. ($2\leq N \leq 200\,000$)

The second line of input contains $N$ space-separated integers, each denoting $D_i$, the absorption capacity of each noise barrier. ($1\leq D_i \leq 10^9$)

The third line of input contains $Q$, denoting the number of operations Hyunbin has carried out. ($1\leq Q \leq 200\,000$)

Each of the following $Q$ lines contains an operation in the same format as written in the problem statement. It is guaranteed that at least one type 2 operation will be given in the input.

All input values are integers.

Output

Print the results of all type $2$ operations carried out by Hyunbin, in order, one per line.

Examples

Input 1

6
5 1 2 4 7 3
5
1 2 1
2 3
1 4 7
2 3
2 5

Output 1

3
6
14