题目描述

给定 $(1, 2, \ldots, N)$ 的一个排列 $P = (P_1, P_2, \ldots, P_N)$。

请按顺序处理 $Q$ 个询问，询问有以下两种：

• 1 x y：交换 $P_x$ 与 $P_y$ 的值。
• 2：构造出满足下列条件的排列 $P' = (P'_1, \ldots, P'_N)$，并把 $P_1, \ldots, P_N$ 分别替换成 $P'_1, \ldots, P'_N$（可以证明这样的 $P'$ 唯一存在）：
  • 对每个满足 $1 \le i \le N$ 的整数 $i$，都有 $P_{P'_i} = i$。

（换句话说，第 $2$ 类询问就是把 $P$ 替换成它的逆排列。）

请输出处理完所有询问后的 $P_1, \ldots, P_N$。

输入格式

N Q
P_1 P_2 ... P_N
query_1
...
query_Q

其中每个询问是下面两种格式之一：

1 x y

2

输出格式

在一行中输出处理完所有询问后的 $P_1, \ldots, P_N$，相邻两个数之间用一个空格隔开。

输入示例 1

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

输出示例 1

4 5 2 1 3

示例 1 说明

每处理完一个询问后 $P$ 的变化如下：

• 第 $1$ 个询问（交换第 $2$、$4$ 位）后：$P = (2, 5, 3, 1, 4)$；
• 第 $2$ 个询问（取逆）后：$P = (4, 1, 3, 5, 2)$；
• 第 $3$ 个询问后：$P = (4, 3, 1, 5, 2)$；
• 第 $4$ 个询问后：$P = (4, 3, 5, 1, 2)$；
• 第 $5$ 个询问（取逆）后：$P = (4, 5, 2, 1, 3)$。

输入示例 2

7 4
3 7 5 6 4 2 1
2
2
2
2

输出示例 2

3 7 5 6 4 2 1

示例 2 说明

连续取两次逆等于没变（逆的逆就是自身），所以取 $4$ 次逆之后回到原排列。

输入示例 3

10 8
7 3 2 4 8 5 10 9 1 6
2
1 4 10
1 6 9
2
1 9 10
1 3 10
2
1 4 6

输出示例 3

3 10 2 8 6 7 1 5 9 4

示例 3 说明

这组数据里交换与取逆交替出现，且最后一次操作是交换（不是取逆）。它专门用来检验：在「当前表示的是逆排列」的状态下做交换时，有没有改对数组、有没有同步修复另一份数组。

约束条件

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $(P_1, \ldots, P_N)$ 是 $(1, \ldots, N)$ 的排列
• 第 $1$ 类询问中 $1 \le x < y \le N$
• 所有输入值均为整数