可持久化线段树 1（可持久化数组）

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

维护一个长度为 $n$ 的数组。初始数组称为版本 $0$。你需要依次执行 $m$ 次操作，第 $i$ 次操作会在某个已有版本 $v$ 的基础上生成版本 $i$。

操作有以下两种：

1. 将版本 $v$ 中位置 $p$ 的值修改为 $c$，得到新版本 $i$；
2. 查询版本 $v$ 中位置 $p$ 的值，并令新版本 $i$ 与版本 $v$ 完全相同。

输入格式

第一行包含两个正整数 $n,m$，分别表示数组长度和操作数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示版本 $0$ 的数组。

接下来 $m$ 行描述操作。设当前为第 $i$ 次操作：

• v 1 p c：在版本 $v$ 的基础上将位置 $p$ 的值修改为 $c$；
• v 2 p：查询版本 $v$ 中位置 $p$ 的值，并复制版本 $v$。

输出格式

对于每个查询操作，输出一行一个整数，表示查询结果。

样例输入

5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

样例输出

59
87
41
87
88
46

数据范围

对于所有数据：

• $1\le n,m\le 10^6$；
• $-10^9\le a_i,c\le 10^9$；
• $1\le p\le n$；
• 对于第 $i$ 次操作，$0\le v<i$。

子任务

样例说明

每次操作都会生成一个新版本。查询操作本身不修改数组，因此它生成的版本与所查询的版本完全相同。