题目描述

循环双链表的节点定义如下：

struct Node {
	int val;
	Node *nxt, *pre;
}; 
Node *head; // 头节点
int tot; // 统计节点数量

链表的操作有以下 $8$ 种：

• 1 v，在链表头部插入值为 v 的节点。
• 2 v，在链表尾部插入值为 v 的节点。
• 3 x v，在第一个数据域为 x 的节点后插入值为 v 的节点，如果不存在数据域为 x 的节点，则忽略删除操作。
• 4 x v，在第一个数据域为 x 的节点前插入值为 v 的节点，如果不存在数据域为 x 的节点，则忽略删除操作。
• 5 v，删除数据域为 v 的节点，如果不存在数据域为 v 的节点，则忽略删除操作。
• 6，正序遍历链表，输出所有节点的数据域。
• 7，倒序遍历链表，输出所有节点的数据域。
• 8，输出链表中的节点数量。

格式要求

输入格式

第一行先输入一个整数 $n$，代表操作次数。

接下来 $n$ 行，每行先输入一个整数 $op$，代表操作类型，根据操作类型，会再输入 $x$ 或 $v$。

$5 \leq n \leq 10^4$，$1 \leq op \leq 8$，$1 \leq x, v \leq 10^7$。

输出格式

输出若干行，每行代表操作 $6 \sim 8$ 的一次输出，同一行里的数字间用空格隔开。

样例

12
1 5
2 10
1 3
6
3 5 7
6
4 3 8
6
5 3
6
7
8

3 5 10
3 5 7 10
8 3 5 7 10
8 5 7 10
10 7 5 8
4

样例解释