问题描述

给定一个长度为$N$的序列$A = (A_1, A_2, \dots, A_N)$。 处理$Q$个按顺序给出的查询。

第$q$个$(1\leq q\leq Q)$查询是以下三种格式之一，分别表示以下操作：

• $1\ x _ q$：将$A$中的每个元素赋值为$x_q$。
• $2\ i _ q\ x _ q$：将$x_q$加到$A _ {i _ q}$上。
• $3\ i _ q$：输出$A _ {i _ q}$的值。

约束条件

• $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)$
• 如果第$q$个$(1\leq q\leq Q)$查询是第二种或第三种格式，则$1 \leq i _ q \leq N$。
• 如果第$q$个$(1\leq q\leq Q)$查询是第一种或第二种格式，则$0 \leq x _ q \leq 10^9$。
• 输入中至少有一个第三种格式的查询。
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

N
A_1 A_2 ... A_N
Q
query_1
query_2
...
query_Q

其中，$\operatorname{query}_q$表示第$q$个查询，格式为以下之一：1 x、2 i x、3 i。

输出

输出$X$行，其中$X$是第三种格式查询的数量。

第$j$个$(1\leq j\leq X)$行应包含对第$j$个此类查询的答案。

样例输入1

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

样例输出1

1
8
5

初始时，$A=(3,1,4,1,5)$。

查询处理如下：

• $A_2=1$，输出$1$。
• 将$4$加到$A_3$上，$A$变为$(3,1,8,1,5)$。
• $A_3=8$，输出$8$。
• 将$A$中所有元素赋值为$1$，$A$变为$(1,1,1,1,1)$。
• 将$4$加到$A_3$上，$A$变为$(1,1,5,1,1)$。
• $A_3=5$，输出$5$。

样例输入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

样例输出2

8000000000

注意$A$的元素可能超出32位整数类型的范围。

样例输入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

样例输出3

7
5
7
21
21
19
10