Description

学习完单链表之后，需要你来实现一个双链表，下面是双链表的主要功能：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数；

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

Input Format

第一行包括一个整数M，表示操作次数，接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种:

1. L X ：表示在链表的最左端插入数 X
2. R X ：表示链表的最右端插入数 X
3. D K ：表示将第 K 个插入的数删除
4. IL K X ：表示在第 K 个插入的数左侧插入一个数X
5. IR K X ： 表示在第 K 个插入的数右侧插入一个数X

Output Format

将整个链表从左到右输出

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2​

8 7 7 3 2 9​

Hint

1 ≤ M ≤ 1e5

所有操作保证合法