Problem Statement

You are given $a sequence A = (A_1, A_2, \dots, A_N)$ of length N.
Given Q queries, process all of them in order.
The $q-th (1\leq q\leq Q)$ query is in one of the following three formats, which represents the following queries:

• 1\ x _ q: assign x_q to every element of A.
• 2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
• 3\ i _ q: print the value of A _ {i _ q}.

Input

The input is given from Standard Input in the following format:
N
$A_1 A_2 \dots A_N$
Q
$\operatorname{query}_1$
$\operatorname{query}_2$
$\vdots$
$\operatorname{query}_Q$

Here, $\operatorname{query}_q$ denotes the q-th query, which is in one of following formats: 1 x, 2 i x, and 3 i.

Output

Print X lines, where X is the number of q'$s (1\leq q\leq Q)$ such that $\operatorname{query}_q$ is in the third format.
The $j-th (1\leq j\leq X)$ line should contain the answer to the j-th such query.

Constraints

• $1 \leq N \leq 2\times10^5$
• $1 \leq Q \leq 2\times10^5$
• $0 \leq A _ i \leq 10^9$\ $(1\leq i\leq N)$
• If the $q-th (1\leq q\leq Q)$ query is in the second or third format, $1 \leq i _ q \leq N$.
• If the $q-th (1\leq q\leq Q)$ query is in the first or second format, $0 \leq x _ q \leq 10^9$.
• There exists a query in the third format.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
8
5

Initially, A=(3,1,4,1,5).
The queries are processed as follows:

• A_2=1, so print 1.
• Add 4 to A_3, making A=(3,1,8,1,5).
• A_3=8, so print 8.
• Assign 1 to every element of A, making A=(1,1,1,1,1).
• Add 4 to A_3, making A=(1,1,5,1,1).
• A_3=5, so print 5.

Sample Input 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Sample Output 2

8000000000

Note that the elements of A may not fit into a 32-bit integer type.

Sample Input 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Sample Output 3

7
5
7
21
21
19
10

见题面 Input 部分

见题面 Output 部分