题目描述

Pontus 进入了一个宝藏的面前，但是想要把宝藏拿到需要输入正确密码，否则就会 Die 。

善良的密码设置人还会给来到宝藏面前的人一些提示，“想得到我的宝藏么，那就来……”

那就根据我给你的几行数字，求出最终的密码吧！

第一行为两个数字 $n$ 和 $m$，$n$ 代表初始数列中的数字个数，$m$ 代表会有 $m$ 次操作；

第二行会有 $n$ 个数字 ，空格分隔，代表初始队列中的数字；

接下来 $m$ 行，每行的第一个数字如果是 $1$，接下来就会有两个数字 $x$ 和 $y$，代表在原本数列的第 $x$ 位置上添加 $y$；每行的第一个数字如果是 $2$ ，接下来就会有 $1$ 个数字 $x$，代表删除第 $x$ 位置上的数字。

经过这 $m$ 次操作后得到的数列就是密码，Pontus不想轻易的就 Die，一起来帮 Pontus 解决一下吧！

输入格式

第一行为两个数字 $n$ 和 $m$；

第二行 会有 $n$ 个数字，空格分隔；

接下来会有 $m$ 行，每行 $3$ 个或者 $2$ 个数字。

输出格式

输出一行数字，空格分隔。

样例

样例输入

6 2
11 2 6 31 4 8
1 2 3
2 1

样例输出

3 2 6 31 4 8

数据范围与提示

对于 $100\%$ 的数据，$1\le n,m\le 10^4$，$初始数列中的数、y\le 10^9$。