B Type Shuffle

Bessie has invented two types of card shuffling techniques. The A‐shuffle is performed on a deck of M cards (2 ≤ M ≤ 10⁵) by rearranging them according to a given permutation p. In other words, if the cards are numbered from 1 to M from top to bottom, then in one A‐shuffle the card in position i moves to position p_i (1 ≤ p_i ≤ M). For example, if M = 3 and p = {3, 1, 2}, then one A‐shuffle transforms the deck [1, 2, 3] into [2, 3, 1] because the first card (1) goes to position 3, the second card (2) goes to position 1, and the third card (3) goes to position 2.

Bessie now practices a more complicated shuffling method called the B‐shuffle on a larger deck of N cards (M ≤ N ≤ 10⁹) initially arranged in order 1, 2, …, N (with 1 on top). The B‐shuffle proceeds as follows, using an initially empty temporary pile:

1. If the current deck has at least M cards, take the top M cards and perform an A‐shuffle on them. Otherwise, skip to step 3.
2. Remove the top card from the deck (after the A‐shuffle) and place it on the top of the temporary pile. Then repeat from step 1.
3. Once the deck has less than M cards, simply remove the top card one by one and place it on the temporary pile until no cards remain.

Note that when a card is removed, it is placed on the top of the temporary pile, so the final order of the temporary pile is the reverse of the removal order. Given the permutation p, Bessie would like to know which card ends up at certain positions in the temporary pile after exactly one B‐shuffle.

Input will be in the following format:

• The first line contains three integers: N, M, and Q (the number of queries, 1 ≤ Q ≤ min(N, 5000)).
• The second line contains M integers: p₁, p₂, …, p_M, describing the A‐shuffle permutation. It is guaranteed that p is a permutation of {1, 2, …, M}.
• Then Q lines follow, each containing an integer q_i (1-indexed) representing a query for the card at that position in the final temporary pile (the top card is position 1).

Note: 50% of test cases satisfy N ≤ 10⁵. Although N can be as large as 10⁹, the provided input cases will be small enough so that a correct simulation will pass.

Mathematical formulation: In the rounds when the deck has at least M cards, an A‐shuffle is performed. Let \(f:\{1,2,\dots,M\}\to\{1,2,\dots,M\}\) be defined by

[ f(i)=p_i, ]

and define the transformation on a card already within the top M as follows. If a card is at position \(i\) (1-indexed) and \(p_i \neq 1\) then after the A‐shuffle and removal of the top card it will survive with a new position \(p_i-1\); if \(p_i=1\) it is removed in that round. When there are fewer than M cards a card simply moves one position closer to the top in each removal step.

Your task is to output the number on the card at each queried position in the final temporary pile (which is the reverse of the removal order).

inputFormat

The first line contains three integers: N, M, and Q.

The second line contains M space‐separated integers: p₁ p₂ ... p_M.

The next Q lines each contain one integer: q_i, representing a query (1-indexed) for the final temporary pile (with position 1 being the top).

outputFormat

Output Q lines. The i-th line should contain the number on the card that ends up in the q_i-th position of the temporary pile.

sample

6 3 3
3 1 2
1
3
6

5
4
2

</p>