你有一个数组 $a = (a_1, \dots, a_n)$，初始时包含 $1$ 到 $n$ 的一个排列。你需要处理两类查询：

• “$1 \ p$” ($1 \le p \le n$)：查找当前数组 $a$ 中的 $a_p$；
• “$2 \ p$” ($1 \le p \le n - 1$)：将数组 $a$ 替换为函数 merge 作用于数组 $(a_1, \dots, a_p)$ 和 $(a_{p+1}, \dots, a_n)$ 后的结果。

函数 merge 的逻辑如下：

func merge(var a as array, var b as array)
var c as array
while (a and b have elements)
if (a[0] > b[0])
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
while (a has elements)
add a[0] to the end of c
remove a[0] from a
while (b has elements)
add b[0] to the end of c
remove b[0] from b
return c

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 数组长度和查询次数 ($2 \le n, m \le 2 \cdot 10^5$)。

第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

接下来的 $m$ 行，每行包含两个整数 $t_i$ 和 $p_i$ —— 第 $i$ 次查询的描述 ($t_i \in \{1, 2\}$，$p$ 满足上述格式描述中的约束)。

输出格式

对于每个类型为 $1$ 的查询，在单独的一行中输出答案。

样例

样例输入 1

4 3
4 3 2 1
2 1
2 1
1 2

样例输出 1

1

样例输入 2

5 7
4 3 5 2 1
2 4
2 1
1 3
1 1
2 4
1 4
1 5

样例输出 2

3
1
3
5