题目描述

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

给定 $Q$ 个查询，请依次处理它们。第 $q$ 个查询（$1 \le q \le Q$）属于以下三种格式之一：

• 1 x：将序列 $A$ 中的每个元素都赋值为 $x$。
• 2 i x：将 $x$ 加到元素 $A_i$ 上（即 $A_i \leftarrow A_i + x$）。
• 3 i：输出元素 $A_i$ 的值。

输入格式

第一行包含一个正整数 $N$ —— 表示序列的长度。

第二行包含 $N$ 个非负整数 $A_1, A_2, \dots, A_N$ —— 表示序列的初始元素。

第三行包含一个正整数 $Q$ —— 表示查询的数量。

接下来 $Q$ 行，每行描述一个查询，格式为 1 x、2 i x 或 3 i 中的一种。

输出格式

设在 $Q$ 个查询中，共有 $X$ 个第三种格式的查询。 请输出 $X$ 行，第 $j$ 行（$1 \le j \le 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

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

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

说明

样例解释

在第一个样例中，初始时 $A=(3, 1, 4, 1, 5)$。查询的处理过程如下：

• 询问 3 2：$A_2 = 1$，因此输出 $1$。
• 询问 2 3 4：将 $4$ 加到 $A_3$ 上，此时 $A=(3, 1, 8, 1, 5)$。
• 询问 3 3：$A_3 = 8$，因此输出 $8$。
• 询问 1 1：将 $1$ 赋值给 $A$ 的每个元素，此时 $A=(1, 1, 1, 1, 1)$。
• 询问 2 3 4：将 $4$ 加到 $A_3$ 上，此时 $A=(1, 1, 5, 1, 1)$。
• 询问 3 3：$A_3 = 5$，因此输出 $5$。

数据范围

• 对于所有测试点，保证 $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$）。
• 如果查询是第二种或第三种格式，保证 $1 \le i \le N$。
• 如果查询是第一种或第二种格式，保证 $0 \le x \le 10^9$。
• 保证至少存在一个第三种格式的查询。
• 保证所有的输入数值均为整数。