题目描述

给定一个长度为 $n$ 的初始数组，编号为版本 $0$。接下来进行 $m$ 次操作，每次操作都会产生一个新版本，当前第 $i$ 次操作产生的版本编号为 $i$。

操作分为两种：

• 1 v p x：以版本 $v$ 为基础，将第 $p$ 个数修改为 $x$，产生版本 $i$；
• 2 v p：查询版本 $v$ 中第 $p$ 个数的值，并产生一个与版本 $v$ 完全相同的版本 $i$。

输入格式

第一行包含两个整数 $n,m$。
第二行包含 $n$ 个整数，表示版本 $0$ 的数组。
接下来 $m$ 行，每行表示一次操作，格式见题目描述。

输出格式

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

5 6
1 2 3 4 5
2 0 3
1 0 3 10
2 2 3
1 2 1 -7
2 4 1
2 1 3

3
10
-7
3

数据范围与提示

• $1 \le n,m \le 2\times 10^5$
• $-10^9 \le a_i,x \le 10^9$
• $0 \le v<i$
• $1 \le p \le n$