分数: 1000 点
问题陈述
对于两种排列 p 和 q 中的整数 1 通过 N,让 f(p,q) 是满足以下条件的排列:
- 的 p_i- 第一个元素 (1 \leq i \leq N)在 f(p,q) is q_i。 在这里, p_i 和 q_i 分别表示 i- 第一个元素 p 和 q.
你有两种排列 p 和 q 中的整数 1 通过 N。 我们现在将定义一个序列{a_n} 的整数排列 1 通过 N,如下:
- a_1=p, a_2=q
- a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )
给定一个正整数 K,查找 a_K.
约束
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- p 和 q 是来自以下整数的排列 1 通过 N.
输入
输入由标准输入按以下格式给出:
N K p_1 ... p_N q_1 ... q_N
输出
打印 N 整数,中间有空格。 的 i- 第一个整数 (1 \leq i \leq N)应该是 i- 第一个元素 a_K.
示例输入 1
3 3 1 2 3 3 2 1
示例输出 1
3 2 1
自从 a_3=f(p,q),我们只需要找到 f(p,q)。 我们有 p_i=i 在这里,所以 f(p,q)=q.
示例输入 2
5 5 4 5 1 2 3 3 2 1 5 4
示例输出 2
4 3 2 1 5
示例输入 3
10 1000000000 7 10 6 5 4 2 9 1 3 8 4 1 9 2 3 7 8 10 6 5
示例输出 3
7 9 4 8 2 5 1 6 10 3