说明

现有一个长度为n的正整数序列，对这个数组进行m次操作，可以对序列进行的操作分为以下两类：<o:p></o:p>

输入1 i v： 表示在序列中第i个元素前加入新的元素v；<o:p></o:p>

输入2 i：   表示删除序列中的第i个元素。<o:p></o:p>

注意：两类操作都要满足 i <= n

输入格式

第1行：n和d，表示序列的初始长度和最后查询的元素下标<o:p></o:p>

第2行：n个用空格间隔的数，表示原始的序列<o:p></o:p>

第3行：m，表示操作的次数 <o:p></o:p>

接下来的m行分别是每次对序列进行的操作（题目描述中的三类操作中的一种）

输出格式

最终操作完毕后查询的元素值,如果没有此元素则输出-1

样例

5 3
6 7 8 9 10
3
1 2 12
2 3
1 3 4

4