问题陈述

给你一个 $(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'$ 唯一存在）。
  • $P_{P'_i} = i$ 满足 $1 \leq i \leq N$ 的每一个整数 $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 \leq x < y \leq N 用于 $1$ 类型的查询。
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

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

这里， $\mathrm{query}_q$ 代表 $q$ -th 查询，并以以下两种格式之一给出：

$1$ $x$ $y$

$2$

输出

在处理完所有查询后，将 $P_1, \dots, 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

在处理完每个查询后， $P_1, \dots, P_N$ 的值如下：

• 处理完第一个查询后， $P = (2,5,3,1,4)$ 。
• 处理第二个查询后， $P = (4,1,3,5,2)$ 。
• 处理第三个查询后， $P = (4,3,1,5,2)$ 。
• 处理完第四个查询后， $P = (4,3,5,1,2)$ 。
• 处理完第五次查询后， $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

输入样本 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