考虑一个包含 $n$ 个元素的多重集 $A = \{a_1, a_2, \dots, a_n\}$。

我们定义两种可以在该多重集上执行的操作：

1. 给定 $x_i$，你需要输出将多重集按非递减顺序排序后，第 $x_i$ 小的元素。
2. 给定 $x_i$，你需要将 $A$ 中所有严格大于 $x_i$ 的元素减去 $x_i$。

你的任务是按给定顺序执行 $q$ 次操作，并输出所有第一类操作的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$：多重集 $A$ 的大小和询问次数（$1 \le n \le 10^5$，$1 \le q \le 10^6$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）：$A$ 中的元素。

接下来的 $q$ 行，每行描述一个操作。操作由两个整数 $t_i$ 和 $x_i$ 给出：操作的类型和参数。保证 $t_i \in \{1, 2\}$。若 $t_i = 1$，则 $1 \le x_i \le n$。若 $t_i = 2$，则 $1 \le x_i \le 10^9$。

保证至少存在一个第一类操作。

请注意，$A$ 中的元素以任意顺序给出。

输出格式

对于每个第一类操作，输出排序后第 $x_i$ 小的元素。用换行符分隔答案。

样例

输入 1

4 5
1 5 6 12
2 5
1 1
1 2
1 3
1 4

输出 1

1
1
5
7

输入 2

5 4
1 10 5 4 2
2 1
1 5
2 3
1 2

输出 2

9
1

输入 3

3 2
3 2 1
2 10000
1 3

输出 3

3