题目描述

请你实现一个支持多种基础操作的单链表。 给定一个初始长度为 $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$ 开始动态计算。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(0 \le n \le 10^5, 1 \le q \le 10^5)$，分别表示初始链表的长度和操作的次数。 第二行包含 $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 6
10 20 30 40 50
search 30
insert 2 25
delete 4
update 5 55
search 40
delete 100

样例输出

3
4
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. delete 100：当前链表长度为 5，第 100 个节点不存在，无效操作，链表不变。 最后输出修改完毕后的链表：10 20 25 40 55。