大唐的大理寺的审讯犯人和捉拿犯人的部门，大理寺人员众多，往往需要派出去很多进行抓捕犯人，由于老大需要坐镇大理寺，所以每次派出去的都是二号人物。

下面给出大理寺的原有n个人员战斗力序列a_1,a_2,\dots,a_n；

有m次的调入和调出（朝廷会委派新人进入）命令，请你输出每次调出人员的战斗力！

数据保证都能有人派出去，0\leq a_i

第一行一个数字n和m，表示人员数量和调令数量

第二行n个数字a_i，表示当前大理市人员的战斗力

接下来m行，每行为1个或者2个数字，1后面没有数字，表示派人出去查案

2和x表示上级派进一个新的人，战斗力为x

k次输出，表示1后面调出去的人的战斗力

样例解释，第一次派出去的是2因为当前战斗力序列是3，2，1，然后放进来两个人，目前的战斗力序列就是5，3，2，1，然后派出去的就是3

70%数据，m,n\leq 500;

100%数据，m,n\leq 10^5,a_i\leq 10^9