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.