[USACO13DEC] The Bessie Shuffle G

Bessie is practicing her card tricks. She has already mastered the Bessie- shuffle -- a shuffle on M (2 <= M <= 100,000) cards that reorganizes the cards so the i-th card from the top is now the P[i]-th card from the top. Now Bessie is practicing shuffles on larger decks. She has a deck of N cards (M <= N <= 1,000,000,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. 50% of test cases will have N <= 100,000. 贝西有一种独门的洗牌方法，称为 A 类洗牌法； A 类洗牌法的具体过程：将一堆共 $M$（$2 \le M \le 10 ^ 5$）张从上到下编号 $1, 2, \cdots, M$ 的纸牌，从上到下第 $i$ 张牌洗到位置 $p _ i$。 例如，$M=3，p = \{3, 1, 2\}$，则执行一次 A 类洗牌法后，从上到下将变为 $2, 3, 1$，即牌 $1$ 放到位置 $3$，牌 $2$ 放到位置 $1$，牌 $3$ 放到位置 $2$。 贝西现在要练习另外一种洗牌方法，称为 B 类洗牌法。 B 类洗牌法的具体过程： 有一堆 $N$（$M \le N \le 10 ^ 9$）张编号为 $1, 2, \cdots, N$ 的牌，并按从上到下 $1$ 到 $N$ 的顺序堆放。另有一个牌堆用来辅助洗牌，称为临时堆，开始时为空。 1. 将最上面 $M$ 张牌进行一次 A 类洗牌法； 2. 将最上面的一张牌放到临时堆的最上方； 3. 重复前两个操作，直到原先的堆没有牌为止。 以上过程中，当原先堆的牌不足 $M$ 张的时候，将不进行 A 类洗牌法，而是将最上面的牌依次放到临时堆上。 给定 $N, M$ 和排列 $p$。现在有 $Q$（$1 \le Q \le \min(N, 5000)$）个询问，请求出对其做一次 B 类洗牌法后临时堆中 $q _ i$ 位置上的牌的编号。 $50\%$ 的数据中，$N \le 10 ^ 5$。

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

\* Lines 1..Q: On the i-th line, print a single integer indicating the card at position q\_i from the top.

5 3 5 
3 
1 
2 
1 
2 
3 
4 
5 

4 
5 
3 
1 
2 

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. The shuffle proceeds as: ```plain [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] 贝西的五张牌刚开始顺序为 [1, 2, 3, 4, 5]。她一次洗三张牌，效果是将第一张牌放到底部。以上五个问题询问了每一张牌的位置。 洗牌的顺序是: ```plain [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正面向下放置) ``` 这就形成了最终的顺序：[4, 5, 3, 1, 2]