题目描述

食堂窗口前，编号为 $1 \sim n$ 的 $n$ 名同学按编号从小到大排成一队（$1$ 号在队头）。

接下来依次发生了 $q$ 个事件，事件有三种：

• 1 x y：同学 $x$ 离开原来的位置，插到同学 $y$ 的后面；
• 2 x y：同学 $x$ 离开原来的位置，插到同学 $y$ 的前面；
• 3 x：同学 $x$ 离开队伍，不再回来。

保证每个事件中提到的同学当时都在队伍里，且 $x \ne y$。保证最后队伍中至少还有 $1$ 名同学。

请输出所有事件发生后，队伍从队头到队尾的编号。

输入格式

第一行两个整数 $n, q$。

接下来 $q$ 行，每行一个事件，格式为 1 x y、2 x y 或 3 x。

输出格式

一行若干个整数，表示最后队伍从队头到队尾的编号，相邻两个数之间用一个空格隔开。

样例 #1

样例输入 #1

5 4
1 2 4
2 5 1
3 3
1 1 2

样例输出 #1

5 4 2 1

样例解释

提示

数据范围

• 对于 $40\%$ 的数据：$n, q \le 1000$；
• 对于 $100\%$ 的数据：$2 \le n \le 10^5$，$1 \le q \le 10^5$。

提示

• 如果用普通数组存队伍，每次插入、删除都要把后面的元素挪一遍，最坏要 $10^{10}$ 次操作，会超时。
• 用双向链表：L[x]、R[x] 分别记录 $x$ 前面和后面的同学。删除和插入都只需要改几个指针，是 $O(1)$ 的。
• 可以增加一个编号为 $0$ 的「哨兵」结点，让 R[0] 指向队头、L[0] 指向队尾，把队伍连成一个环，这样插到队头、队尾时就不用特殊处理了。
• 「插到 $y$ 前面」就是「插到 $y$ 的前一个人的后面」。