【知识点】
【双向链表】
单向链表里的每个数据都只有一个指针，但我们可以把指针设定为两个，并且让它们分别指向前后数据，这就是“双向链表”。使用这种链表，不仅可以从前往后，还可以从后往前遍历数据，十分方便。

和单向链表相比：
1、双向链表没有头结点概念。
2、增加一个前驱指针。

【数组模拟】
和 STL 的 list 类相比，使用数组模拟链表速度更快，但是代码量不大。这点代价我们还是可以接受的。
使用一个一维数组来模拟链表，注意元素只是增加不会减少。所以定义 MAXN  的时候需要使用 $2$ 倍的容量。
需要实现的操作有插入元素，删除元素。
【链表的定义】

const int MAXN=1e6+10;
LL e[MAXN];  //保存链表元素
LL L[MAXN];  //保存上一个结点，注意是数组 e 的下标。
LL R[MAXN];  //保存下一个结点，注意是数组 e 的下标。
LL idx;          //数组用到那个元素

【链表的初始化】
我们约定：
1、e[0] 用来保存队首节点。
2、e[1] 用来保存队尾节点。
3、R[0] 为队首节点下标。
4、L[1] 为队尾节点下标。

如下图所示。
tle="" align="" />
这个时候双向队列是里面没有任何元素。我们将队首节点的下一个节点指向队尾节点，如下图所示。对应的 C++ 为 R[0]=1; 也就是队首节点的一下节点为下标编号是 $1$ 的节点。
tle="" align="" />
我们将队尾节点的下一个节点指向队首节点，如下图所示。对应的 C++ 为 L[1]=0; 也就是队为节点的一下节点为下标编号是 $0$ 的节点。
tle="" align="" />

void init() {
    R[0]=1;//第一个点的右边是 1
    L[1]=0;//第二个点的左边是 0
    idx=2;  //已经使用了两个位置，分别是队首和队尾
}

【插入元素】
在下标为 K 个点右边插入一个 $X$，如下图所示：
tle="" align="" />
第一步：生成一个节点，该节点的下标为 idx。如下图所示。对应的 C++ 代码为 e[idx]=x;
tle="" align="" />
第二步：将该结点的上一个节点设置为 k，即前驱节点是下标为 k 的结点。如下图所示。对应的 C++ 代码为 L[idx]=k;
tle="" align="" />
第三步：将该结点的下一个节点设置为前驱节点 k 的后继节点 R[k]，即后继节点是下标为 R[k] 的结点。如下图所示。对应的 C++ 代码为 R[idx]=R[k];
 tle="" align="" />
第四步：将编号为 k 的结点的下一个结点的前驱节点指向 idx。如下图所示。对应的 C++ 代码为 L[R[k]]=idx;
tle="" align="" />
第五步：将编号为 k 的结点的下一个结点的前驱节点指向 idx。如下图所示。对应的 C++ 代码为 R[k]=idx;
tle="" align="" />
第六步：移动到下一个存储位置。对应的 C++ 代码为 idx++;
这样我们就完成了在下标为 k 的结点后面（右边）插入一个新的节点。对应的完整代码如下。

void add(LL x, LL k) {
    e[idx]=x;  //将 x 保存到下标为 idx 的位置
    L[idx]=k;
    R[idx]=R[k];
    L[R[k]]=idx;
    R[k]=idx;
    idx++;
}

【删除元素】
删除下标为 k 节点。当前节点状态如下图所示。
tle="" align="" />
第一步，将下标为 R[K] 的结点的前驱节点变为 L[k]。如下图所示。对应的 C++ 代码为 L[R[k]]=L[k];
tle="" align="" />
第二步，将下标为 L[K] 的结点的后继节点变为 R[k]。如下图所示。对应的 C++ 代码为 R[L[k]]=R[k];
tle="" align="" />
这样就完成了将下标为 k 的结点删除。对应的完整代码如下。

void remove(LL k) {
    L[R[k]]=L[k];
    R[L[k]]=R[k];
}

【遍历链表】

//从左到右遍历
for (LL i=R[0]; i!=1; i=R[i]) {
    cout<<e[i]<<" ";
}
//从右到左遍历
for (LL i=L[1]; i!=0; i=L[i]) {
    cout<<e[i]<<" ";
}

【循环链表】
我们也可以在链表尾部使用指针，并且让它指向链表头部的数据，将链表变成环形。这便是“循环链表”，也叫“环形链表”。



【任务】
给定一个 $N$ 个数的构成的双向链表，$M$ 次操作，每次操作为下列操作之一。
操作 $1\ x$：在双向链表的最左端插入数字 $x$。
操作 $2\ x$：在双向链表的最右端插入数字 $x$。
操作 $3\ k\ x$：在第 $k$ 个插入的数左侧插入一个数 $x$。
操作 $4\ k\ x$：在第 $k$ 个插入的数右侧插入一个数 $x$。
操作 $5 \ k$：表示将第 $k$ 个插入的数删除。

第一行包括两个整数 $N\ (1 \leq N \leq 10^4),\ M\ (1 \leq M \leq 10^2)$，$N$ 表示原有的双向链表元素个数，$M$ 表示操作次数。
第二行包括 $N$ 个数字 $a_i,\ (-10^9 \leq a_i \leq 10^9)$。
接下来 $M$ 行，每行包含一个操作命令，具体操作看题目描述。
保证所有操作保证合法。

共 $m$ 组输出，每组输出包括四行。
第一行输出：op:x，其中 $x$ 表示第几次操作。具体看样例输出。
第二行若干个数将整个链表从左到右输出。
第三行若干个数将整个链表从右到左输出。
第四行为一个空行。