시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 1 1 1 100.000%

문제

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.

예제

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.

구현

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 attachments.zip.

입력

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).

출력

The sample judge will write $N$ lines with the return values of clip(I).

제한

  • $N, K \le 100\,000$
  • $2 \le M \le 10^9$

예제 입력 1

4 2
3 2 1 0
2
3 1

예제 출력 1

0 2

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > KATT2 A번

  • 문제를 만든 사람: Johan Sannemo

제출할 수 있는 언어

C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.