问题描述

给定一个长度为$N$的序列$A = (A_1, A_2, \dots, A_N)$。

给定$Q$个查询，按顺序处理它们。第$q$个$(1\leq q\leq Q)$查询可以有以下三种格式之一，分别表示以下查询：

• $1\ x_q$：将$x_q$赋值给$A$的每个元素。
• $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$ $\dots$ $A_N$ $Q$ $\operatorname{query}_1$ $\operatorname{query}_2$ $\vdots$ $\operatorname{query}_Q$

这里，$\operatorname{query}_q$表示第$q$个查询，它可以是以下格式之一：1 x，2 i x 和 3 i。

输出

打印$X$行，$X$是$q$的数量$(1\leq q\leq Q)$，满足$\operatorname{query}_q$是第三种格式。第$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$。
• 将$1$分配给$A$的每个元素，得到$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