数列查询

题目描述

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

给定 $Q$ 个查询,按给出的顺序依次处理。每个查询为以下两种之一:

• 1 k x:将 $A_k$ 的值设为 $x$。
• 2 k:输出 $A_k$ 的值。

输入格式

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

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$Q$
$\operatorname{query}_1$
$\operatorname{query}_2$
$\vdots$
$\operatorname{query}_Q$

其中,$\operatorname{query}_i$ 表示第 $i$ 个查询,格式为以下两种之一:

$1$ $k$ $x$

$2$ $k$

输出格式

输出 $q$ 行,其中 $q$ 为第二种查询的个数。第 $j$ 行 $(1\leq j\leq q)$ 输出第 $j$ 个第二种查询的答案。

样例

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

3
5
0
8
1

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

对于第 $1$ 个查询,$A=(1,3,5)$,其中 $A_2=3$,因此应输出 $3$。

对于第 $2$ 个查询,$A=(1,3,5)$,其中 $A_3=5$,因此应输出 $5$。

第 $3$ 个查询将 $A_3$ 的值设为 $0$,使 $A=(1,3,0)$。

对于第 $4$ 个查询,$A=(1,3,0)$,其中 $A_3=0$,因此应输出 $0$。

第 $5$ 个查询将 $A_2$ 的值设为 $8$,使 $A=(1,8,0)$。

对于第 $6$ 个查询,$A=(1,8,0)$,其中 $A_2=8$,因此应输出 $8$。

对于第 $7$ 个查询,$A=(1,8,0)$,其中 $A_1=1$,因此应输出 $1$。

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

2
16
0
0
16
100

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

478
317
838
838
176
595
468

数据范围

• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $0 \le A_i \le 10^9\ (1\leq i\leq N)$
• 所有查询满足 $1\leq k\leq N$。
• 所有第一种查询满足 $0\leq x\leq 10^9$。
• 至少有一个第二种查询。
• 输入中的所有值均为整数。