Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program to process the following queries:

• 1 i j k: Add $k$ to each of $A_i, A_{i+1}, \ldots, A_j$.
• 2 x: Output $A_x$.

Input

The first line contains an integer $N$ ($1 \le N \le 100{,}000$), the length of the sequence.

The second line contains $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 1{,}000{,}000$).

The third line contains an integer $M$ ($1 \le M \le 100{,}000$), the number of queries.

The next $M$ lines each contain one query. For queries of type 1, it holds that $1 \le i \le j \le N$, $-1{,}000{,}000 \le k \le 1{,}000{,}000$; for queries of type 2, it holds that $1 \le x \le N$. There is at least one query of type 2.

Output

For each query of type 2, output one line with the answer.

Examples

Input 1

5
1 2 3 4 5
4
1 3 4 6
2 3
1 1 3 -2
2 3

Output 1

9
7