Video Clips
On a popular web site, the $N$ KATT contestants can spend time watching video clips in between solving problems.
On the site, there are $K$ funny videos of cats jumping around on the keyboard, numbered between $0$ and $K - 1$. When one of the videos has been viewed, a suggestion for the next funny cat video is shown, which you of course click on and start watching.
For each contestant, you will be given the initial cat video he or she views. Determine what the $M$:th video that each contestant watches will be.
Example
In total, there are $N = 2$ contestants, and $K = 4$ cat videos. The suggestion for each of the videos are $(3, 2, 1, 0)$. The first contestant starts to watch video $3$, and the second starts to watch video $1$. We wonder what the $M = 3$:rd clip each contestant views is.
The first contestant will start by watching video 3. From there, she looks at the suggested video 0, and is then led back to video 3.
The second contestant starts out with the second video, which links to the third video. Video $2$ has video $1$ as suggestion, so he ends up back on video 1.
Task
Your task is to compute, for each contestant, what the $M$:th video he or she will watch is. You will implement the functions videos(K, M, S) and clip(I).
-
videos(K, M, S) - this function will be called exactly once by the judge at the start of the execution.
-
K: the number of funny cat videos.
-
M: the number of videos each contestant will watch.
-
S: an array with $K$ elements. S[i] ($0 \le i < N$) contains the suggested video for the $i$:th video.
-
$0 \le S[i] < K$
-
The function has no return value.
-
-
clip(I) - this function will be called once for every contestant.
-
I: a number between $0$ and $K - 1$; the video that a contestant starts watching.
-
The function should return the $M$:th video the contestant will watch, if she starts on video $I$.
-
A code skeleton containing the functions to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/videoclips.zip.
Subtasks
The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.
Let $N$ be the number of calls to clip(I).
|
Subtask |
Points |
Limits |
|
1 |
15 |
$N, K \le 100\, 000$, $2 \le M \le 10^9$, the $i$:th video will only suggest videos $j$ such that $j \le i$. |
|
2 |
15 |
$N, K \le 100\, 000$, $2 \le M \le 10^9$, all videos will suggest each other in a cycle (e.g $3$ suggest $2$ suggest $0$ suggest $1$ suggest $3$, för $N = 4$). |
|
3 |
15 |
$N, K \le 1\, 000$ $2 \le M \le 1\, 000$ |
|
4 |
15 |
$N, K \le 1\, 000$, $2 \le M \le 10^9$ |
|
5 |
40 |
$N, K \le 100\, 000$, $2 \le M \le 10^9$ |
Input format
The sample judge reads input in the following format:
-
line $1$: K M
-
line $2$: S[0] ... S[K - 1]
-
line $3$: N: the number of calls made to clip(I).
-
line $4$ I1 ... IN: the parameters of the $N$ calls to clip(I).
Output format
The sample judge will write $N$ lines with the return values of clip(I).
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 3 2 1 0 2 3 1 |
0 2 |
