Problem Statement

You are given a permutation $P = (P_1, \dots, P_N)$ of $(1, \dots, N)$.

Process $Q$ queries in order. There are two types of queries as follows:

• 1 x y: Swap the values of $P_x$ and $P_y$.
• 2: Construct the permutation $P' = (P'_1, \dots, P'_N)$ of $(1, \dots, N)$ satisfying the following condition, and replace the values of $P_1, \dots, P_N$ with $P'_1, \dots, P'_N$, respectively. (One can prove that such $P'$ uniquely exists.)
  • $P_{P'_i} = i$ for every integer $i$ satisfying $1 \leq i \leq N$.

Output the values of $P_1, \dots, P_N$ after processing all queries.

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $(P_1, \dots, P_N)$ is a permutation of $(1, \dots, N)$.
• $1 \leq x < y \leq N$ for queries of type $1$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Here, $\mathrm{query}_q$ represents the $q$-th query, and is given in one of the following two formats:

$1$ $x$ $y$

$2$

Output

Output the values of $P_1, \dots, P_N$ after processing all queries, separated by spaces, on one line.

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

4 5 2 1 3

At the point when each query has been processed, the values of $P_1, \dots, P_N$ are as follows:

• After processing the first query, $P = (2,5,3,1,4)$.
• After processing the second query, $P = (4,1,3,5,2)$.
• After processing the third query, $P = (4,3,1,5,2)$.
• After processing the fourth query, $P = (4,3,5,1,2)$.
• After processing the fifth query, $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

• Source: AtCoder ABC 470 D