#4923. [Lydsy1706月赛]K小值查询

内存限制:256 MiB 时间限制:15 Sec

题目描述

维护一个长度为n的正整数序列a_1,a_2,...,a_n,支持以下两种操作:
1 k,将序列a从小到大排序,输出a_k的值。
2 k,将所有严格大于k的数a_i减去k。

输入格式

第一行包含两个正整数n,m(1<=n,m<=100000),分别表示序列的长度和操作的个数。
第二行包含n个正整数a_1,a_2,...,a_n(1<=a_i<=10^9),分别表示序列中的每个元素。
接下来m行,每行两个正整数op(1<=op<=2),k,若op=1,则1<=k<=n;若op=2,则1<=k<=10^9;依次描述每个操作。

输出格式

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

样例

样例输入


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

样例输出


			
1
1
5
7

数据范围与提示