Migrated from Lutece 2755 卷卷人的计划表

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

明日复明日，明日何其多。为了按时完成每天的任务，每个卷卷人都会给自己做个计划表，这个计划表按时间列出了卷卷人接下来要完成的任务。这个计划表并不是不变的，有时候也会有新的任务要放在两个任务间完成。现在卷卷人要去卷了，希望你能写个程序帮忙完成这个计划表。

计划表中的任务用一个 $[0,10^9]$ 的数字表示，这个计划表需要实现的操作有：

1、在第 $pos$ 个任务前插入一个任务 $k$ 2、查询第 $pos$ 个任务是什么

Input

第一行两个整数 $N,M$，表示初始时任务的个数和操作数
第二行 $N$ 个整数表示初始时的计划表
接下来 $M$ 行，每行第一个整数 $opt$ 表示操作的种类

$opt=1$，之后有两个数 $k,pos$，表示在第 $pos$ 个任务前插入一个任务 $k$，如果 $pos$ 大于当前的任务数，则表示把任务加到计划表里当前任务的最后一个后面 $opt=2$，之后有一个数 $pos$，表示询问第 $pos$ 个任务是什么

Output

对于操作 $2$，输出一个整数表示答案

Samples

2 8
1 2
2 1
2 2
1 3 2
1 4 4
1 5 2
2 5
1 6 1
2 3

1
2
4
5

Constraints

保证计划表长度不超过 $10^6$
$1 \le pos \le 10^6 , 0 \le k \le 10^9 , 1 \le M \le 10^5$ 保证询问的位置一定在当前计划表中

Resources

2022 UESTC ICPC Training for Data Structures