题目描述

实现一个双链表，双链表初始为空，支持 5 种操作：

1.在最左侧插入一个数；

2.在最右侧插入一个数；

3.将第 k 个插入的数删除；

4.在第 k 个插入的数左侧插入一个数；

5.在第 k 个插入的数右侧插入一个数

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。

R x，表示在链表的最右端插入数 x。

D k，表示将第 k 个插入的数删除。

IL k x，表示在第 k 个插入的数左侧插入一个数。

IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出 1≤M≤100000 所有操作保证合法。

样例

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

提示

出自acwing，侵删。 原题链接 https://www.acwing.com/problem/content/829/ ——蔡祥龙，有问题发q173661289