Videoklipp

På en populär hemsida så kan de $N$ deltagarna i KATT titta på videoklipp mellan deras problemlösning.

På sajten finns det $K$ roliga videoklipp med katter som hoppar runt på ett tangentbord, numrerade mellan $0$ och $K - 1$. När man tittat på en av videoklippen följer ett förslag på nästa kattvideo, som du såklart klickar på och börjar titta på.

För varje tävlanden får du den ursprungliga kattvideon hen tittade på. Avgör vilken den $M$:te kattvideon varje tävlanden tittar på blir.

Exempel

Totalt har vi $N = 2$ tävlanden, och $K = 4$ kattvideor. Förslagen för varje video är $(3, 2, 1, 0)$. Den första tävlanden börjar med att titta på video 3, och den andra börjar på video 1. Vi undrar vilka de $M = 3$:e videoklippen blir för de två tävlanden.

Den första tävlanden börjar med att titta på video 3. Därefter tittar hon på video 0, och sist återigen på video 3.

Den andra börjar på andra videon, som länkar till den tredje. Video 2 har video 1 som förslag, så han hamnar till slut på video 1 återigen.

Uppgift

Din uppgift är att beräkna, för varje tävlanden, vad den $M$:te videon hen tittar på blir. Du ska implementera funktionerna videos(K, M, S) och clip(I).

videos(K, M, S) - denna funktion anropas exakt en gång av domaren i början av programmet.
- K: antalet roliga kattvideor.
- M: antalet videor varje tävlanden ska kolla på.
- S: en array med $K$ element. S[i] ($0 \le i < N$) innehåller förslaget för video $i$.
- $0 \le S[i] < K$
- Funktion har inget returvärde

clip(I) - denna funktion anropas en gång för varje deltagare.
- I: ett tal mellan $0$ och $K - 1$; videon som tävlanden börjar titta på.
- Funktionen ska returnera den $M$:te videon som deltagaren kommer titta på, om hon börjar på video $I$.

Ett kodskelett som innehåller funktionerna du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/videoclips.zip.

Delpoäng

Problemet består av flera grupper av testfall. Varje grupp ger ett visst antal poäng och för att klara det måste du klara alla testfall i gruppen.

Låt $N$ vara antalet anrop till clip(I).

Grupp	Poäng	Gränser
1	15	$N, K \le 100\, 000$, $2 \le M \le 10^9$, den $i$:te videon kommer enbart föreslå en video $j$ så att $j \le i$.
2	15	$N, K \le 100\, 000$, $2 \le M \le 10^9$, alla videoklipp kommer föreslå varandra i en cykel (exempelvis $3$ föreslår $2$ föreslår $0$ föreslår $1$ föreslår $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$

Indataformat

Exempeldomaren läser indata i följande format:

rad $1$: K M
rad $2$: S[0] ... S[K - 1]
rad $3$: N: antalet anrop till clip(I).
rad $4$ I1 ... IN: parametrarna till de $N$ anropen till clip(I).

Utdataformat

Exempeldomaren skriver ut $N$ rader med returvärdena från clip(I).

Sample Input 1	Sample Output 1
4 2 3 2 1 0 2 3 1	0 2