베시는 그녀의 카드 트릭을 연습하고 있습니다. 그녀는 이미 베시-셔플이라는 신기술을 완벽하게 익혔는데, 베시-셔플은 위에서부터 i번째 (1 <= i <= M, 1 <= M <= 100,000)에 있는 카드를 P[i]번째로 옮깁니다.

베시는 좀 더 커다란 카드 꾸러미에서 카드를 섞으려고 합니다. 그녀는 현재 N개의 (M <= N <= 100,000) 카드로 이루어진 꾸러미를 갖고 있으며, 위에서부터 1~N번 카드가 순서대로 놓여 있습니다. 그녀는 위쪽 M개의 카드를 베시-셔플한 후 가장 위의 카드를 다른 꾸러미로 옮깁니다. 베시는 카드가 M-1개 남을 때까지 이를 반복하며, 마지막에는 카드가 남지 않을 때까지 가장 위의 카드를 계속 옮깁니다.

베시는 카드가 잘 섞였는 지 알아보기 위해 새로운 카드 꾸러미에서의 k번째(위에서부터) 카드가 몇 번 카드인지 총 Q번 확인할 것입니다. (1 <= Q <= N, Q <= 5,000)

베시를 도와 새로운 카드 꾸러미의 k번째 카드가 몇 번 카드인지 답하는 프로그램을 작성하세요.

입력

• Line 1: N, M, Q 가 입력됩니다.
• Lines 2..1+M: i+1번째 줄에는 베시-셔플에서 i번째 카드가 옮겨질 지점 P[i]가 입력됩니다. (1 <= P[i] <= M).
• Lines 2+M..1+M+Q: i+1+M번째 줄에는 베시의 i번째 질문을 나타내는 정수 k_i 가 입력됩니다. 당신은 새로운 카드 꾸러미의 k_i번째 카드가 몇 번인지 구해야 합니다. (1 <= k_i <= N).

출력

• Lines 1..Q: i번째 줄에 새로운 카드 꾸러미의 k_i번째 카드의 번호를 출력합니다.

입출력 예

입력 

5 3 5 
3 
1 
2 
1 
2 
3 
4 
5 

출력 

4 
5 
3 
1 
2 

입출력 보충 설명

베시는 5개의 카드로 이루어진 카드꾸러미를 갖고 있고 [1, 2, 3, 4, 5]의 순서로 놓여 있습니다. 그녀의 베시-셔플은 첫 번째 카드를 세 번째 위치로 옮깁니다. 베시는 5번의 질문을 합니다.

출력 예 설명:

베시는 다음과 같이 카드를 섞을 것입니다:

• [1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (2번 카드 이동)
• [3, 1, 4, 5] -> [1, 4, 3, 5] (1번 카드 이동)
• [4, 3, 5] -> [3, 5, 4] (3번 카드 이동)
• [5, 4] (5번 카드 이동)
• [4] (4번 카드 이동)

Now Bessie is practicing shuffles on larger decks. She has a deck of N cards (M <= N <= 100,000) conveniently labeled 1 to N. She shuffles this deck by taking the first M cards and performing the Bessie-shuffle on them, placing the shuffled cards back on top of the deck. She then removes the top card from the deck and places it face down. She repeats this process, placing the top cards successively on top of each other, until she is out of cards. When Bessie has less than M cards left, she no longer performs the Bessie-shuffle, but continues to place the top card on top of the others.

Bessie knows that the deck initially started in sorted order, with 1 on top, 2 next, and N on the bottom. Given the description of the Bessie-shuffle, help Bessie compute which cards end up located at Q different specified positions (1 <= Q <= N, Q <= 5,000) in the deck.

입력

• * Line 1: A single line containing N, M and Q separated by a space.
• * Lines 2..1+M: Line i+1 indicates the position from the top, P[i], of the i-th card in the Bessie-shuffle (1 <= P[i] <= M).
• * Lines 2+M..1+M+Q: Line i+1+M contains a single integer q_i describing the i-th query. You are to compute the label on the card located in position q_i from the top (1 <= q_i <= N).

출력

입출력 예

입력

5 3 5
3
1
2
1
2
3
4
5

출력

4
5
3
1
2

INPUT DETAILS:

Bessie has a deck of 5 cards initially ordered as [1, 2, 3, 4, 5].  Her
shuffle is on 3 cards and has the effect of moving the top card to the
bottom.  There are 5 queries querying each position in the deck.

OUTPUT DETAILS:

The shuffle proceeds as:

[1, 2, 3, 4, 5] -> [2, 3, 1, 4, 5] (put 2 face down)
[3, 1, 4, 5] -> [1, 4, 3, 5] (put 1 face down)
[4, 3, 5] -> [3, 5, 4] (put 3 face down)
[5, 4] (put 5 face down)
[4] (put 4 face down)

This produces the final order of [4, 5, 3, 1, 2]

출처:usaco/2013/dec/silver
번역:functionx