YOUTUBE  Youtube
N students are bored in computer class so they watch funny video clips on YouTube.
The site contains K popular clips, numbered 1 through N. When a video clip is watched, a list of similar video clips is displayed on the side.
Every student picks a video clip from the main page and starts watching it. After exactly one minute every student gets bored of his or her video clip, so he opens the first video clip from the list of similar clips on the side (even if he already watched that clip).
Write a program that determines for each student which video clip he will be watching during the Mth minute of the class.
Input
The first line contains three integers N, K and M (1 ≤ N, K ≤ 100 000) (1 < M ≤ 1 000 000 000), the numbers of students, video clips and minutes.
The second line contains N integers, each between 1 and K, the indices of video clips the students start watching.
The third line contains K integers, each between 1 and K, the index of the first similar clip for each video clip.
Output
Output N integers, the indices of video clips that students will be watching during the Mth minute.
Example
Input:
4 5 2
1 2 4 3
5 5 1 2 3
Output: 5 5 2 1
Input:
2 6 5
1 6
2 3 4 1 4 5
Output:
1 2
hide comments
markomafko95:
20180515 21:11:38
Hint: think like LCA 

orange:
20130630 15:24:50
don't spam here!!!


darryl:
20130623 14:46:42
it can be solved without looking for cycles... 

Archit Mittal:
20130115 16:56:02
tough one... 

Troy:
20120628 07:27:18
can be done without using cycles... has an easy implementation, like dat of suffix array... 

MyTh:
20120617 18:34:35
giving tle with normal logic of finding cycle.. plz help.. 

cool_frog:
20120612 16:00:05
Giving time limit error !!!! Any hints plz .... 

Smit Mehta:
20120115 14:26:19
6354341 : It is giving a seg fault after 12 judges!! kindly see it. 

a.out:
20110820 17:34:33
Don't know which test case i'm missing running fine on my pc and it's giving wrong answer. 

Lewin Gan:
20110728 18:25:14
Note: if you have a 2d array with bounds [x][y], where x > y, you can get a speed up by switching to bounds [y][x] 
Added by:  Stjepan Glavina 
Date:  20110221 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Croatian Nationals 2009 