置换游戏

题目描述

小桐有一个长度为 $n$ 的序列 $\{x_i\}$，其中每个元素都在 $1$ 到 $n$ 之间。她还有另一个长度为 $n$ 的序列 $\{a_i\}$。

她准备对 $\{a_i\}$ 进行一种神奇的操作，一共操作 $k$ 次。每次操作是这样的：

• 构造一个新的序列 $\{b_i\}$，其中 $b_i = a_{x_i}$（也就是把 $a$ 按照 $x$ 指定的位置重新排列）；
• 然后把 $\{b_i\}$ 赋值给 $\{a_i\}$，作为下一次操作的基础。

她想知道，经过 $k$ 次操作之后，$a$ 序列会变成什么样子？

输入格式

输入第一行两个整数 $n$ 和 $k$。

第二行 $n$ 个整数 $[x_1, x_2, \ldots, x_n]$。

第三行 $n$ 个整数 $[a_1, a_2, \ldots, a_n]$。

输出格式

输出一行 $n$ 个整数，表示 $k$ 次操作后的 $\{a_i\}$ 序列。

数据范围

• 对于 $30\%$ 的数据，$k \leq 100$；
• 对于另外 $30\%$ 的数据，$|x_i-i| \leq 1$；
• 对于 $100\%$ 的数据，$1 \le n \le 2\cdot 10^5$，$0 \le k \le 10^{18}$，$1 \le x_i \le n$，$1 \le a_i \le 2\cdot 10^5$。

样例数据 1

输入：

7 3
5 2 6 3 1 4 6
1 9 1 9 8 1 7

输出：

8 9 1 9 1 1 1

样例数据 2

输入：

4 0
3 4 1 2
1 9 1 9

输出：

1 9 1 9

样例数据 3

输入：

9 100453580998244353
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