题目背景

UPDATE : 最后一个点时间空间已经放大

2021.9.18 增添一组 hack 数据 by @panyf

标题即题意

有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）

题目描述

如题，你需要维护这样的一个长度为 $N$ 的数组，支持如下两种操作：

1. 在某个历史版本上修改某一个位置上的值。

2. 访问某个历史版本上的某一位置的值。

此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 $1$ 开始编号，版本 $0$ 表示初始状态数组）。

对于操作 $2$，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。

输入格式

输入的第一行包含两个正整数 $N, M$，分别表示数组的长度和操作的个数。

第二行包含 $N$ 个整数，依次为初始状态下数组各位的值（依次为 $a_i$，$1 \leq i \leq N$）。

接下来 $M$ 行每行包含 $3$ 或 $4$ 个整数，代表两种操作之一（设当前是第 $i$ 次操作）：

1. 对于操作 $1$，格式为 v 1 p c，即为在版本 $v$ 的基础上，将 $a_{p}$ 修改为 $c$。

2. 对于操作 $2$，格式为 v 2 p，即访问版本 $v$ 中的 $a_{p}$ 的值，注意：生成一样版本的对象应为 $v$。

输出格式

输出包含若干行，依次为每个操作 $2$ 的结果。

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

提示

数据规模

对于 $30\%$ 的数据，$1 \leq N, M \leq {10}^3$。

对于 $50\%$ 的数据，$1 \leq N, M \leq {10}^4$。

对于 $70\%$ 的数据，$1 \leq N, M \leq {10}^5$。

对于 $100\%$ 的数据：

• $1 \leq N, M \leq {10}^6$；
• $1 \leq p \leq N$；
• 设当前是第 $x$ 次操作，$0 \leq v < x$；
• $-{10}^9 \leq a_i,c \leq {10}^9$。

样例说明

所有操作结束后，总共生成了 $11$ 个版本，编号为 $0 \sim 10$，依次为：

版本 $0$：59 46 14 87 41，

版本 $1$：59 46 14 87 41，

版本 $2$：14 46 14 87 41，

版本 $3$：57 46 14 87 41，

版本 $4$：88 46 14 87 41，

版本 $5$：88 46 14 87 41，

版本 $6$：59 46 14 87 41，

版本 $7$：59 46 14 87 41，

版本 $8$：88 46 14 87 41，

版本 $9$：14 46 14 87 41，

版本 $10$：59 46 14 87 91。