← 返回题目列表

Codeforces · 683/H

H. 交换书籍

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

n个爱读书的小学生,在学校学习。众所周知,每个学生都有一个最好的朋友,并且每个学生都是另一个学生最好的朋友。每个学生都有一本有趣的书。

学生们决定互相分享书籍。每天,所有学生都会把自己的书送给最好的朋友。这样,每个学生每天都有一本书。

你的任务是使用最好的朋友列表并确定 k 天后学生之间的书籍交换。为简单起见,所有测试中的所有学生均编号为 1 到 n。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 1016) — 学生数量和交换书籍的天数。

第二行包含n个不同的整数ai(1≤ai≤n),其中ai等于拥有编号为i的最好朋友的学生的编号。

可以保证,没有一个学生是自己最好的朋友。

输出

在一行中打印n个不同的整数,其中第i个整数应该等于k天后将拥有这本书的学生的编号,该学生在开始时拥有该书。

示例

输入 #1

4 1
2 4 1 3

输出 #1

3 1 4 2

输入 #2

5 5
3 4 5 2 1

输出 #2

3 4 5 2 1

输入 #3

6 18
2 3 5 1 6 4

输出 #3

1 2 3 4 5 6

注意

第一个测试的解释。

有4名学生,1天。最好的朋友列表等于{2,4,1,3}。这意味着:

- 数字3的学生 - 是数字1的学生最好的朋友,
- 数字1的学生 - 是数字2的学生最好的朋友,
- 数字 4 的学生 - 是数字 3 的学生最好的朋友,
- 2号学生 - 是4号学生最好的朋友。

第一天之后,交换书籍将是{3,1,4,2}。

- 数字 3 的学生将拥有数字 1 的学生一开始拥有的书,
- 数字1的学生将拥有数字2的学生一开始拥有的书,
- 数字 4 的学生将拥有数字 3 的学生一开始拥有的书
- 数字 2 的学生将拥有数字 4 的学生一开始拥有的书。

因此,答案是 3 1 4 2。