题目描述

请你实现并维护一个支持多种基础操作的双向链表。 给定一个初始长度为 $n$ 的双向链表，随后需要处理 $q$ 次操作。操作分为以下四种：

1. 增 (insert k v)：在当前双向链表的第 $k$ 个节点之后插入一个值为 $v$ 的新节点。

• 如果 $k = 0$，表示在双向链表的最头部（首个节点之前）插入新节点，新节点将成为新的头节点。
• 如果 $k \ge$ 当前链表长度，表示在双向链表的最尾部插入新节点，新节点将成为新的尾节点。

2. 删 (delete k)：删除当前双向链表中的第 $k$ 个节点。

• 如果 $k \le 0$ 或者 $k >$ 当前链表长度，则判定为无效操作，链表保持不变。

3. 查 (search x)：从头到尾遍历当前双向链表，查找首次出现值为 $x$ 的节点，并立刻输出该节点的正向序号（占一行）。

• 如果整个链表中都不存在值为 $x$ 的节点，请输出 -1。

4. 改 (update k v)：将当前双向链表中的第 $k$ 个节点的值修改为 $v$。

• 如果 $k \le 0$ 或者 $k >$ 当前链表长度，则判定为无效操作，链表保持不变。

注意：

• 所有操作中的节点编号均从头节点开始，正向动态计算（即编号为 $1, 2, 3, \dots$）。
• 在进行插入和删除操作时，请务必确保双向链表的前驱（prev）和后继（next）指针均被正确维护。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(0 \le n \le 10^3, 1 \le q \le 10^3)$，分别表示初始双向链表的长度和操作的次数。 第二行包含 $n$ 个整数，表示初始双向链表从头到尾各个节点的值（若 $n=0$，则此行为空）。 接下来的 $q$ 行，每行包含一个操作指令，格式为上述四种之一：

• insert k v
• delete k
• search x
• update k v

其中所有涉及的节点序号 $k$ 和节点值 $x, v$ 均满足 $[-10^9 \le k, x, v \le 10^9]$。

输出格式

对于每一次 search 操作，输出一行一个整数，表示查找的结果。 在处理完所有的 $q$ 次操作后，最后单独输出一行，包含最终双向链表从头到尾所有节点的值，数字之间用一个空格隔开。如果最终链表为空，请输出单词 empty。

样例输入

5 7
10 20 30 40 50
search 30
insert 2 25
delete 4
update 5 55
search 40
insert 0 5
delete 100

样例输出

3
4
5 10 20 25 40 55

样例说明

初始链表：10 20 30 40 50

1. search 30：30 在第 3 个位置，输出 3。
2. insert 2 25：在第 2 个节点后插入 25，链表变为 10 20 25 30 40 50。
3. delete 4：删除第 4 个节点（原值为 30），链表变为 10 20 25 40 50。
4. update 5 55：将第 5 个节点的值改为 55，链表变为 10 20 25 40 55。
5. search 40：40 在当前链表的第 4 个位置，输出 4。
6. insert 0 5：$k=0$ 代表在最头部插入 5，链表变为 5 10 20 25 40 55。
7. delete 100：当前链表长度为 6，第 100 个节点不存在，属于越界无效操作，链表不变。

最终按从头到尾的顺序输出修改完毕后的双向链表：5 10 20 25 40 55。