E - Permute K times 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

(1,2,\ldots,N) の並べ替え P=(P _ 1,P _ 2,\ldots,P _ N) が与えられます。

次の操作を K 回行います。

  • i=1,2,\ldots,N に対して同時に P _ i を P _ {P _ i} で更新する

すべての操作を終えたあとの P を出力してください。

制約

  • 1\leq N\leq2\times10 ^ 5
  • 1\leq K\leq10 ^ {18}
  • 1\leq P _ i\leq N\ (1\leq i\leq N)
  • P _ i\neq P _ j\ (1\leq i\lt j\leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
P _ 1 P _ 2 \ldots P _ N

出力

操作をすべて行ったあとの P について、P _ 1,P _ 2,\ldots,P _ N をこの順に空白を区切りとして出力せよ。

入力例 1

6 3
5 6 3 1 2 4

出力例 1

6 1 3 2 4 5

それぞれの操作によって、P は次のように変化します。

  • 1 回目の操作の結果、P=(2,4,3,5,6,1) となります。
  • 2 回目の操作の結果、P=(4,5,3,6,1,2) となります。
  • 3 回目の操作の結果、P=(6,1,3,2,4,5) となります。

よって、6 1 3 2 4 5 を出力してください。

入力例 2

5 1000000000000000000
1 2 3 4 5

出力例 2

1 2 3 4 5

P _ i=i なので、何度操作を行っても P は変化しません。

入力例 3

29 51912426
7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16

出力例 3

18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20

Score : 475 points

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

The following operation will be performed K times:

  • For i=1,2,\ldots,N, simultaneously update P_i to P_{P_i}.

Print P after all operations.

Constraints

  • 1\leq N\leq2\times10^5
  • 1\leq K\leq10^{18}
  • 1\leq P_i\leq N\ (1\leq i\leq N)
  • P_i\neq P_j\ (1\leq i\lt j\leq N)
  • All input values are integers.

Input

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

N K
P_1 P_2 \ldots P_N

Output

For the P after all operations, print P_1,P_2,\ldots,P_N in this order, separated by spaces.

Sample Input 1

6 3
5 6 3 1 2 4

Sample Output 1

6 1 3 2 4 5

With each operation, P changes as follows:

  • After the first operation, P is (2,4,3,5,6,1).
  • After the second operation, P is (4,5,3,6,1,2).
  • After the third operation, P is (6,1,3,2,4,5).

Thus, print 6 1 3 2 4 5.

Sample Input 2

5 1000000000000000000
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Since P_i=i, P does not change no matter how many operations are performed.

Sample Input 3

29 51912426
7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16

Sample Output 3

18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20