D - Inverse and Swap 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

(1, \dots, N) の順列 P = (P_1, \dots, P_N) が与えられます。

Q 個のクエリを順に処理してください。クエリは以下の 2 種類です。

  • 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 番目のクエリを表し、以下の 2 種類のいずれかの形式で与えられる。

1 x y

2

出力

すべてのクエリを処理したあとの P_1, \dots, P_N の値を、空白区切りで 1 行に出力せよ。

入力例 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 の値は以下のようになります。

  • 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)

入力例 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

Score : 400 points

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.

Sample Input 1

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

Sample Output 1

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).

Sample Input 2

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

Sample Output 2

3 7 5 6 4 2 1

Sample Input 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

Sample Output 3

3 10 2 8 6 7 1 5 9 4