题目描述

小明在藏宝库发现了一批宝藏，有一天小明想要清点这些宝藏，于是把$m$堆宝藏放进了宝藏管理系统，每堆宝藏都$i$有一个珍贵植$v_i$，他希望你能编写程序查找到从大到小第$n$珍贵的宝藏，但是现在问题来了，他非常不小心的留了一些宝藏在藏宝库里面，有可能要往现有的系统中添加宝藏，这些宝藏的个数比较少，他表示非常抱歉，但还是希望你的系统能够起到作用。

输入格式

第一行两个整数 $m,q$，表示已经取出来的宝藏个数以及接下来的查询或插入操作个数。

第二行 $m$ 个正整数，表示这 $m$ 个宝藏的珍贵值。

以下 $q$ 行，每行两个整数 $c,n$。

若 $c=1$（即询问），则输出当前第 $n$ 珍贵的宝藏。

若 $c=2$（即插入），则往系统中插入珍贵值为 $n$ 的宝藏。

输出格式

对于每个 $c=1$（询问）,输出当前第 $n$ 珍贵的宝藏的珍贵值 $v_i$。

样例 #1

样例输入 #1

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

样例输出 #1

3
1

提示

对于 $50\%$ 的数据，没有 $c=2$ 的情况；

对于 $100\%$ 的数据，$m\leq 100000$，$c=2$ 的情况不超过 $30000$ 次，$q\leq 30000$，$1 \leq v_i \lt 2^{31}$。