单链表操作

题目描述

有一个单向链表，初始包含 $n$ 个互不相同的正整数，顺序与输入相同。

之后有 $q$ 次操作：

• 1 x y：在值为 x 的结点后插入一个新结点 y；
• 2 x：查询值为 x 的结点后面的元素。若 x 是尾结点，输出 0；
• 3 x：删除值为 x 的结点后面的结点。如果 x 已经是尾结点，则不进行任何操作。

保证执行操作时 x 一定在当前链表中；新插入的 y 在此前从未出现过。

输入格式

第一行两个整数 $n,q$。

第二行包含初始链表的 $n$ 个整数。

接下来 $q$ 行为操作。

输出格式

对于每个 2 x 操作输出一行答案。

数据范围

$1\le n,q\le 100000$，所有结点值不超过 $10^6$。

样例输入

1 6
1
1 1 99
1 99 50
1 99 75
2 99
3 75
2 1

样例输出

75
99