102783: [AtCoder]ABC278 D - All Assign Point Add

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}$.

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.

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.

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

问题描述

你得到了一个长度为$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$是$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