/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
各要素が 1 以上 N 以下である長さ N の数列 X と、長さ N の数列 A が与えられます。
A に以下の操作を K 回行った結果を出力してください。
- B_i=A_{X_i} なる B を新たな A とする
制約
- 入力は全て整数
- 1 \le N \le 2 \times 10^5
- 0 \le K \le 10^{18}
- 1 \le X_i \le N
- 1 \le A_i \le 2 \times 10^5
入力
入力は以下の形式で標準入力から与えられる。
N K X_1 X_2 \dots X_N A_1 A_2 \dots A_N
出力
操作後の A を A' としたとき、以下の形式で出力せよ。
A'_1 A'_2 \dots A'_N
入力例 1
7 3 5 2 6 3 1 4 6 1 2 3 5 7 9 11
出力例 1
7 2 3 5 1 9 3
この入力では X=(5,2,6,3,1,4,6) で、操作前の数列 A=(1,2,3,5,7,9,11) です。
- 操作を 1 度行うと、数列は (7,2,9,3,1,5,9) となります。
- 操作を 2 度行うと、数列は (1,2,5,9,7,3,5) となります。
- 操作を 3 度行うと、数列は (7,2,3,5,1,9,3) となります。
入力例 2
4 0 3 4 1 2 4 3 2 1
出力例 2
4 3 2 1
操作が一度も行われない場合もあります。
入力例 3
9 1000000000000000000 3 7 8 5 9 3 7 4 2 9 9 8 2 4 4 3 5 3
出力例 3
3 3 3 3 3 3 3 3 3
Score : 450 points
Problem Statement
You are given a sequence X of length N where each element is between 1 and N, inclusive, and a sequence A of length N.
Print the result of performing the following operation K times on A.
- Replace A with B such that B_i = A_{X_i}.
Constraints
- All input values are integers.
- 1 \le N \le 2 \times 10^5
- 0 \le K \le 10^{18}
- 1 \le X_i \le N
- 1 \le A_i \le 2 \times 10^5
Input
The input is given from Standard Input in the following format:
N K X_1 X_2 \dots X_N A_1 A_2 \dots A_N
Output
Let A' be the sequence A after the operations. Print it in the following format:
A'_1 A'_2 \dots A'_N
Sample Input 1
7 3 5 2 6 3 1 4 6 1 2 3 5 7 9 11
Sample Output 1
7 2 3 5 1 9 3
In this input, X=(5,2,6,3,1,4,6) and the initial sequence is A=(1,2,3,5,7,9,11).
- After one operation, the sequence is (7,2,9,3,1,5,9).
- After two operations, the sequence is (1,2,5,9,7,3,5).
- After three operations, the sequence is (7,2,3,5,1,9,3).
Sample Input 2
4 0 3 4 1 2 4 3 2 1
Sample Output 2
4 3 2 1
There may be cases where no operations are performed.
Sample Input 3
9 1000000000000000000 3 7 8 5 9 3 7 4 2 9 9 8 2 4 4 3 5 3
Sample Output 3
3 3 3 3 3 3 3 3 3