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 K. 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
sandeep pandey: 2011-07-09 18:08:40

Nice Problem:-):)

Last edit: 2011-07-22 21:40:26
Seshadri R: 2011-03-15 03:30:15

@afid eri (and others with similar request):
Let us take the second test case:
2 6 5 => two students, six clips and five minutes
1 6 => first student starts with clip 1, second (and last) student with 6
2 3 4 1 4 5 => clip 1's similar clip is 2, clip 2's similar clip is 3,
clip 3's similar clip is 4, ... clip 6's similar clip is 5.

Second student watches clip 6 during first minute
He watches clip 5 during second minute
Then, he goes to clip 4 (5th in the list of 2 3 4 1 4 5) during third minute.
clip 1 => minute 4
clip 2 => minute 5
....

Mohit Sinha: 2011-03-07 19:37:01

Do we have to input using enter or spacebar?
My code is running fine on my computer, but here the TL is being exceeded.

abhijith reddy d: 2011-02-26 15:59:26

Shouldn't it be "The site contains K popular clips, numbered 1 through K." instead of "The site contains K popular clips, numbered 1 through N."

afid eri: 2011-02-26 08:24:30

anyone has further explanation? i'm dizzy understanding the test case @_@

Alex Anderson: 2011-02-21 22:02:36

For the second test case:
There is a student watching video clip 6. He watches this for the first minute. Then he clicks the first choice on the side bar, which is 5. So he watches video 5 for the 2nd minute. Then he clicks the first choice on the sidebar, which is 4,

etc.

Radhakrishnan Venkataramani: 2011-02-21 21:47:25

can anyone xplain the test cases?


Added by:Stjepan
Date:2011-02-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian Nationals 2009