Migrated from Lutece 2534 三仙归洞

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

三仙归洞是一个古老的戏法，在表演中，表演者会用到两个碗以及三个小球，通过独特的手法技巧以及迷惑性的表演，能够产生三个小球在两个碗之间自由瞬移或者消失的错觉。

现在我们将这一古老戏法扩展到 $n$ 个碗和 $n$ 个小球，要想实现真正的「$n$ 仙归洞」显然有些困难，现在试着从最简单的手法开始练习。

经过一段时间的练习，你觉得自己实在是太笨了，仍然不能很好的掌握最简单的手法。这时候你开始求助你的大哥。大哥说要想学会灵活的手法，先得拥有一双锐利的眼睛，说着说着，大哥从身后掏出了 $n$ 个碗和 $n$ 个球，然后将碗排成一行。每个球都有一个编号，大哥将球被盖在碗底下，使得每个碗底下都恰好有一个球，而碗看不出区别来，然后大哥嘴角邪魅一笑，说道：「看清楚咯！」。转瞬间，大哥的手开始疯狂地躁动起来，犹如出水蛟龙，顺滑矫健，又犹如天上的闪电，无影无踪。只见大哥的手在各个碗之间飞速地移动着，将各个碗的位置互相交换着，不一会儿就停了一下，并且各个碗仿佛还是最初的样子。然后大哥想考考你，现在从左到右的每个碗底下的小球编号分别是多少。你很稍微想了一会儿，由于你有非常强大的记忆力，你轻松地记住了改变位置时的碗底下的小球编号，因此你说出了正确答案。

但大哥说那只是开胃小菜，现在他会做出更加复杂的手法，而你面临更加严峻地挑战，即你需要在大哥的一番表演后正确说出从左到右每个碗底下的小球编号，只有答对所有答案你才能去学习更加进阶的手法。当然你觉得这个问题对你来说还是太简单了，因此你最终一定能学会 $n$ 仙归洞的！

Input

第一行输入两个整数 $n,q\ (1\le n,q\le 5\times 10^5)$，分别代表有 $n$ 个无区别的碗，$n$ 个编号 $1\sim n$ 的小球，和接下来大哥的 $q$ 次操作。

第二行输入 $n$ 个整数代表从左到右每个碗底下的小球编号。

接下来的 $q$ 行每行都是大哥的一次操作，操作有如下四种类型 $(x\ne y)$：

• $\texttt{1 x y}$：代表大哥将编号为 $x$ 的小球对应的碗放到了编号为 $y$ 的小球对应的碗的右边；
• $\texttt{2 x y}$：代表大哥将编号为 $x$ 的小球对应的碗放到了编号为 $y$ 的小球对应的碗的左边；
• $\texttt{3 x y}$：代表大哥将编号为 $x$ 的小球对应的碗和编号为 $y$ 的小球对应的碗的位置互换；
• $\texttt{4}$：代表大哥使出了顶尖手法，使得所有碗的位置发生了反转，即原来位置为 $1$ 的碗变成了位置为 $n$，原来位置为 $2$ 的碗变成了位置为 $n-1$……原来位置为 $k$ 的碗变成了位置为 $n-k+1$……原来位置为 $n$ 的碗变成了位置为 $1$。

Output

按从左到右的顺序输出最终每个碗底下对应的小球编号即可，答案输出一行。

Samples

4 4
1 2 3 4
1 2 3
2 1 4
3 1 3
4

4 3 2 1

Resources

2021 UESTC ICPC Training for Data Structures