题目背景

小杨的书架两端都能放书、也能取书。

题目描述

书架一开始是空的。接下来有 $m$ 次操作，每次是下面四种之一：

• 1 x：在书架的最左边放一本编号为 $x$ 的书；
• 2 x：在书架的最右边放一本编号为 $x$ 的书；
• 3：从书架的最左边拿走一本书；
• 4：从书架的最右边拿走一本书。

保证不会从空书架上拿书。请输出最终书架上从左到右的书号；如果书架为空，输出 empty。

输入格式

第一行一个整数 $m$。

接下来 $m$ 行，每行一个操作，格式如上（1、2 后面跟一个整数 $x$，3、4 后面没有数字）。

输出格式

一行：从左到右依次输出书架上的书号，书号之间用一个空格分隔；若书架为空则输出 empty。

输入输出样例 #1

输入 #1

6
1 10
2 20
1 5
4
3
2 99

输出 #1

10 99

样例解释

• 1 10：书架 $10$；
• 2 20：书架 $10\ 20$；
• 1 5：书架 $5\ 10\ 20$；
• 4（拿走最右边）：书架 $5\ 10$；
• 3（拿走最左边）：书架 $10$；
• 2 99：书架 $10\ 99$。

所以输出 10 99。

说明/提示

• $1 \le m \le 100000$
• $1 \le x \le 10^9$
• 保证 3、4 操作时书架不为空
• 请用双向链表实现：在两端插入、删除时注意维护好表头和表尾。