时间限制：1秒　　内存限制：256M

---

【题目描述】

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

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

　　此外，每进行一次操作（对于操作 2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）

【输入格式】

　　输入的第一行包含两个正整数 \(N，M\) ， 分别表示数组的长度和操作的个数。
　　第二行包含 \(N\) 个整数，依次为初始状态下数组各位的值（依次为 (a_i ,1≤i≤N)）。
　　接下来 \(M\) 行每行包含 3 或 4 个整数，代表两种操作之一（ \(i\) 为基于的历史版本号）：
　　对于操作 1，格式为：\(v_i\ 1\ loc_i\ value_i\) ，即为在版本 \(v_i\)的基础上，将 \(a_{loc_i}\) 修改为 \(value_i\)
　　对于操作 2，格式为：\(v_i\ 2\ loc_i\)，即访问版本 \(v_i\) 中的 \(a_{loc_i}\) 的值

【输出格式】

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

【输入输出样例】

　Input

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

　Output

59
87
41
87
88
46

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤N,M≤10^3\)
　　对于 \(50\%\) 的数据，\(1≤N,M≤10^4\)
　对于 \(70\%\) 的数据，\(1≤N,M≤10^5\)
　　对于 \(100\%\) 的数据，\(1≤N,M≤10^6，1≤loc_i≤N，0≤v_i<i,−10^9≤a_i，value_i≤10^9\)

【来源】

　　Mr.he**