AT_agc031_d.[AGC031D] A Sequence of Permutations

给定两个由 $1$ 到 $N$ 组成的排列 $p$ 和 $q$，定义排列 $f(p, q)$ 满足以下条件：

• 对于 $f(p, q)$ 的第 $p_i$ 项，其值为 $q_i$。其中，$p_i$ 和 $q_i$ 分别表示排列 $p$ 和 $q$ 的第 $i$ 项的值。

给定两个由 $1$ 到 $N$ 组成的排列 $p$ 和 $q$。定义由 $1$ 到 $N$ 的排列组成的序列 $\{a_n\}$，如下所示：

• $a_1 = p$，$a_2 = q$
• $a_{n+2} = f(a_n, a_{n+1})$（$n \geq 1$）

给定正整数 $K$，请你求出 $a_K$。

输入以如下格式从标准输入读入：

$N$ $K$ $p_1$ ... $p_N$ $q_1$ ... $q_N$

请输出 $N$ 个整数，以空格分隔。第 $i$（$1 \leq i \leq N$）个数表示 $a_K$ 的第 $i$ 项的值。

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^9$
• $p$ 和 $q$ 都是 $1$ 到 $N$ 的排列。

样例解释 1

由于 $a_3 = f(p, q)$，只需求出 $f(p, q)$ 即可。在本例中，$p_i = i$，因此 $f(p, q) = q$。

由 ChatGPT 4.1 翻译