题目描述

$1$ から $N$ の整数からなる $2$ つの順列 $p$ と $q$ に対して、順列 $f(p,q)$ を以下を満たす順列として定めます。

• $f(p,q)$ の $p_i$ ($1\ \leq\ i\ \leq\ N$) 項目の値は $q_i$ である。 ただし, $p_i$, $q_i$ はそれぞれ $p$, $q$ の $i$ 項目の値を表している。

$1$ から $N$ の整数からなる $2$ つの順列 $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$ 項目の値を出力せよ。

题目大意

题目描述

给定两个长为 $n$ 的排列 $p,q$，设 $f(p,q)$ 为使第 $p_i$ 个数为 $q_i$ 的排列。已知 $a_1=p,a_2=q,a_{n+2}=f(a_n,a_{n+1})$。求 $a_k$.

数据范围

$n\le 10^5,k\le 10^9$.

3 3
1 2 3
3 2 1

3 2 1

5 5
4 5 1 2 3
3 2 1 5 4

4 3 2 1 5

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

7 9 4 8 2 5 1 6 10 3

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ K\ \leq\ 10^9$
• $p$ と $q$ は $1$ から $N$ の順列である。

Sample Explanation 1

$a_3=f(p,q)$ であるから、$f(p,q)$ が求められればよいです。 この場合は $p_i=i$ なので、$f(p,q)=q$ となります。