← 返回题目列表

AtCoder · agc031_d

D. 排列序列

中文机器翻译题面 查看原题

分数: 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