7846 - 试题G:体前屈大赛 20'

通过次数

81

提交次数

247

时间限制 : 3 秒
内存限制 : 512 MB

某校的火柴部部长拟定向筋肉部发起一场特别的活动:体前屈大赛

比赛流程是:公布规则->体前屈测试->颁发奖牌

比赛规则:初始参赛人员共有n人,已知在体前屈测试后会有q次特殊事件t发生:

  • t=1类事件:中途加入一名隐藏选手,已知他的体前屈成绩为k;
  • t=2类事件:将所有参赛人员根据体前屈成绩从左到右升序排序,并给从左到右数第k个选手颁发倒霉奖

注:颁发了倒霉奖牌的选手仅仅是拥有奖牌,奖牌不会影响这位选手原来的性质与作用。

体前屈测试:在体前屈测试中初始参赛人员每人都会有一个体前屈成绩ai。

颁发奖牌:你是一名有一说一的纯路人裁判,颁发奖牌的任务降临到了你的头上

在你每一次颁发奖牌时,都要报出这位倒霉的选手的体前屈成绩!

请你利用你的计算机优势,编写一个程序, 根据已知条件输出每一次颁发奖牌时, 你需要报出的成绩。

输入

第一行输入2个整数n, q

第二行输入n个整数a_i(- 1000≤a_i < 1000)

3至(q+ 2)行每行输入2个整数

t, k(1\le t\le 2,\begin{cases} -1000\le k \le 1000,t=1\\ 1\le k\le n, t = 2\end{cases})

能够保证至少有一个t = 2,即不会出现没有输出的情况。

输出

对于每个t = 2输出1个整数

样例

输入

5 8
-1000 1000 4 -5 0
2 1
2 2
2 3
2 4
2 5
1 -1000
2 1
2 2

输出

-1000
-5
0
4
1000
-1000
-1000

提示

数据规模

对于10\%的数据,1 \le n \le 10, 1\le q \le 10

对于40\%的数据,1 \le n \le 5000, 1\le q \le 200

对于100\%的数据,1 \le n \le 10^6, 1\le q \le 10000

来源

竞码编程-蓝桥杯校内选拔赛(决赛)重现赛