整体赋值与单点加

题目描述

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

给定 $Q$ 条查询,按顺序处理全部查询。 第 $q$ 条查询 $(1\le q\le Q)$ 是以下三种格式之一,分别表示如下查询:

$1\ x_q$:将 $A$ 的每个元素都赋值为 $x_q$。

$2\ i_q\ x_q$:将 $x_q$ 加到 $A_{i_q}$ 上。

$3\ i_q$:输出 $A_{i_q}$ 的值。

输入格式

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

$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$ 是满足 $\operatorname{query}_q$ 为第三种格式的 $q$ $(1\le q\le Q)$ 的个数。 第 $j$ 行 $(1\le j\le X)$ 应输出第 $j$ 条此类查询的回答。

样例

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

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$。

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

8000000000

注意 $A$ 的元素可能无法放进 32 位整数类型中。

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

7
5
7
21
21
19
10

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $0 \le A_i \le 10^9$ $(1\le i\le N)$
• 如果第 $q$ 条查询是第二种或第三种格式,则 $1 \le i_q \le N$。
• 如果第 $q$ 条查询是第一种或第二种格式,则 $0 \le x_q \le 10^9$。
• 存在至少一条第三种格式的查询。
• 输入中的所有值均为整数。