题目描述

又一个学期结束了，又积累了好多本书，你决定好好整理一下。整理时共有三种操作，规则如下：

1. 1 p 表示把编号为 p 的书放到最前面
2. 2 p 表示把编号为 p 的书放到最后面
3. 3 p q 表示把编号为 p 的书放到编号为 q 的书的后面

其中，p、q 表示书的编号，操作中的数字之间用空格分隔。已知在整理之前，所有书从 1 开始依次编号排放。

输入格式

共 m+1 行：

• 第一行有两个正整数 n 和 m，分别表示 n 本书和 m 次整理操作
• 接下来的 m 行，每行有 2 个或 3 个由空格分隔的整数，分别对应上述三种整理操作

输出格式

共 1 行，输出整理后的书本顺序，书本间用空格隔开。

输入样例 #1

10 4  
1 3  
2 4  
3 3 6  
3 1 5

输出样例 #1

2 5 1 6 3 7 8 9 10 4

题目说明

1 ≤ n, m ≤ 100000