该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意

维护一个长度为 $n$ 的正整数序列 $a_i$ ，支持以下两种操作：

• $1$ $k$ ，将序列 $a_i$ 从小到大排序，输出 $a_k$ 的值。

• $2$ $x$ ，将所有严格大于 $x$ 的数 $a_i$ 减去 $x$。

输入格式

第一行两个正整数 $n,m(1 \le n,m \le 10^5)$，分别表示序列的长度和操作的个数。

第二行 $n$ 个正整数 $a_i \ (1 \le a_i \le 10^9)$，分别表示序列中的每个元素。

下来 $m$ 行，每行两个整数，表示一次操作（其中 $1 \le k \le n，1 \le x \le 10^9$）。

输出格式

输出若干行，对于每个询问输出一行一个整数，即第 $k$ 小的值。

样例输入

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

样例输出

1
1
5
7