问题描述

给定一个整数 $N$ 和一个长度为 $N$ 的序列 $A=(A _ 1,A _ 2,\\ldots,A _ N)$。

给定 $Q$ 个查询，按照给定的顺序处理它们。每个查询有以下两种类型之一：

• 1 k x ：将值 $A _ k$ 设置为 $x$。
• 2 k ：打印值 $A _ k$。

约束条件

• $1 \\leq N \\leq 10 ^ 5$
• $1 \\leq Q \\leq 10 ^ 5$
• $0 \\leq A _ i \\leq 10 ^ 9\\ (1\\leq i\\leq N)$
• 对于所有的查询，$1\\leq k\\leq N$。
• 对于第一种类型的查询，$0\\leq x\\leq 10 ^ 9$。
• 至少有一个第二种类型的查询。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$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$ 个这样的查询的响应。

示例输入 1

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

示例输出 1

3
5
0
8
1

最初，$A=(1,3,5)$。

• 对于第一个查询，$A=(1,3,5)$，其中 $A _ 2=3$，所以应该打印出 $3$。
• 对于第二个查询，$A=(1,3,5)$，其中 $A _ 3=5$，所以应该打印出 $5$。
• 第三个查询将值 $A _ 3$ 设置为 $0$，使 $A=(1,3,0)$。
• 对于第四个查询，$A=(1,3,0)$，其中 $A _ 3=0$，所以应该打印出 $0$。
• 第五个查询将值 $A _ 2$ 设置为 $8$，使 $A=(1,8,0)$。
• 对于第六个查询，$A=(1,8,0)$，其中 $A _ 2=8$，所以应该打印出 $8$。
• 对于第七个查询，$A=(1,8,0)$，其中 $A _ 1=1$，所以应该打印出 $1$。

示例输入 2

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

2
16
0
0
16
100

示例输入 3

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

示例输出 3

478
317
838
838
176
595
468