103674: [Atcoder]ABC367 E - Permute K times

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

问题陈述

给定一个长度为$N$的序列$X$，其中每个元素都在$1$和$N$之间（包括$1$和$N$），以及一个长度为$N$的序列$A$。
对$A$执行以下操作$K$次，并打印结果。

• 用$B$替换$A$，使得$B_i = A_{X_i}$。

约束条件

• 所有输入值都是整数。
• $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)$。

• 一次操作后，序列变为$(7,2,9,3,1,5,9)$。
• 两次操作后，序列变为$(1,2,5,9,7,3,5)$。
• 三次操作后，序列变为$(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