#P683H. Exchange of Books
-
ID: 3565
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Exchange of Books
No submission language available for this problem.
Description
n pupils, who love to read books, study at school. It is known that each student has exactly one best friend, and each pupil is the best friend of exactly one other pupil. Each of the pupils has exactly one interesting book.
The pupils decided to share books with each other. Every day, all pupils give their own books to their best friends. Thus, every day each of the pupils has exactly one book.
Your task is to use the list of the best friends and determine the exchange of books among pupils after k days. For simplicity, all students are numbered from 1 to n in all tests.
The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 1016) — the number of pupils and days during which they will exchange books.
The second line contains n different integers ai (1 ≤ ai ≤ n), where ai is equal to the number of the pupil who has the best friend with the number i.
It is guaranteed that no pupil is the best friend of himself.
In a single line print n different integers, where i-th integer should be equal to the number of the pupil who will have the book, which the pupil with the number i had in the beginning, after k days.
Input
The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 1016) — the number of pupils and days during which they will exchange books.
The second line contains n different integers ai (1 ≤ ai ≤ n), where ai is equal to the number of the pupil who has the best friend with the number i.
It is guaranteed that no pupil is the best friend of himself.
Output
In a single line print n different integers, where i-th integer should be equal to the number of the pupil who will have the book, which the pupil with the number i had in the beginning, after k days.
Samples
4 1
2 4 1 3
3 1 4 2
5 5
3 4 5 2 1
3 4 5 2 1
6 18
2 3 5 1 6 4
1 2 3 4 5 6
Note
The explanation to the first test.
There are 4 pupils and 1 day. The list of the best friends equals to {2, 4, 1, 3}. It means that:
- the pupil with the number 3 — is the best friend of pupil with the number 1,
- the pupil with the number 1 — is the best friend of pupil with the number 2,
- the pupil with the number 4 — is the best friend of pupil with the number 3,
- the pupil with the number 2 — is the best friend of pupil with the number 4.
After the first day the exchange of books will be {3, 1, 4, 2}.
- the pupil with the number 3 will have the book, which the pupil with the number 1 had in the beginning,
- the pupil with the number 1 will have the book, which the pupil with the number 2 had in the beginning,
- the pupil with the number 4 will have the book, which the pupil with the number 3 had in the beginning
- the pupil with the number 2 will have the book, which the pupil with the number 4 had in the beginning.
Thus, the answer is 3 1 4 2.