题目描述

玩具小火车由若干节车厢首尾相连组成，每节车厢上都有一个编号。调度员会不断下达两种指令：

• 1 p x：在当前第 $p$ 节车厢前插入一节编号为 $x$ 的新车厢；
• 2 p：移走当前第 $p$ 节车厢。

所有操作按顺序执行。请你输出全部操作结束后，小火车从前到后的编号序列。

保证所有操作都是合法的。

输入格式

第一行两个整数 $n,m$，分别表示初始车厢数量和操作数量。

第二行 $n$ 个整数，表示初始车厢编号。

接下来 $m$ 行，每行表示一个操作，格式如题目描述所示。

输出格式

输出一行，表示最终数组中的所有元素，元素之间用一个空格隔开。

如果最后一个元素也没有，输出一行空行。

3 4
1 2 3
1 2 9
2 1
1 4 8
2 2

9 3 8

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 1000$，所有编号的绝对值不超过 $10^9$。