YOUTUBE - Youtube

no tags 

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 M-th 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 M-th 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: 2018-05-15 21:11:38

Hint: think like LCA

orange: 2013-06-30 15:24:50

don't spam here!!!

darryl: 2013-06-23 14:46:42

it can be solved without looking for cycles...

Archit Mittal: 2013-01-15 16:56:02

tough one...

Troy: 2012-06-28 07:27:18

can be done without using cycles... has an easy implementation, like dat of suffix array...

MyTh: 2012-06-17 18:34:35

giving tle with normal logic of finding cycle.. plz help..

cool_frog: 2012-06-12 16:00:05

Giving time limit error !!!! Any hints plz ....

Smit Mehta: 2012-01-15 14:26:19

6354341 : It is giving a seg fault after 12 judges!! kindly see it.

a.out: 2011-08-20 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: 2011-07-28 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:2011-02-21
Time limit:0.373s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian Nationals 2009