Video Clips

Time limit2sMemory limit1024 MB

Summary

For each starting video index, find which video a viewer reaches after watching M videos, where the next video after i is S[i].

Level: Medium6 of 10
Topics: Graph, Binary search, Implementation, Array
Solved: No attempts yet

Problem

On a popular web site, the $N$ KATT contestants watch cat videos between solving problems.

The site has $K$ videos of cats jumping around on a keyboard, numbered from $0$ to $K - 1$ . When a contestant finishes a video, the site suggests the next cat video, and the contestant of course clicks it and starts watching.

You are given the cat video each contestant watches first. Find the $M$ -th video each contestant watches.

Input

The 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

The judge writes $N$ lines with the return values of clip(I).

Constraints

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

Examples1

Example 1
Input
```
4 2
3 2 1 0
2
3 1
```
Expected output
```
0 2
```