题目描述

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

按顺序处理 $Q$ 个询问。询问有以下两种类型：

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

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

数据范围

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $(P_1,\dots,P_N)$ 是 $(1,\dots,N)$ 的一个排列。
• 对于类型 1 的询问，$1 \leq x < y \leq N$。
• 所有输入值均为整数。

输入格式

输入以以下格式从标准输入给出：

• $N$ $Q$
• $P_1$ $P_2$ $\cdots$ $P_N$
• $\mathrm{query}_1$
• $\vdots$
• $\mathrm{query}_Q$

其中 $\mathrm{query}_q$ 表示第 $q$ 个询问，为以下两种格式之一：

• $1$ $x$ $y$

• $2$

输出格式

在一行内输出处理完所有询问后 $P_1,\dots,P_N$ 的值，以空格分隔。

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

4 5 2 1 3

在处理完每个询问的时点，$P_1,\dots,P_N$ 的值如下：

• 处理完第 1 个询问后，$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)$。

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

3 7 5 6 4 2 1

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 10 2 8 6 7 1 5 9 4

• 来源：AtCoder ABC 470 D

子任务设置

• 子任务 1（120 分）：$N,Q \le 2000$。
• 子任务 2（280 分）：无特殊限制。