P3098 [USACO13DEC] The Bessie Shuffle G

Bessie has a unique shuffling method, called the A-shuffle (also called the Bessie-shuffle). A-shuffle: Take a stack of $M$（$2 \le M \le 10 ^ 5$） cards labeled from top to bottom $1, 2, \cdots, M$. Move the $i$-th card from the top to position $p _ i$ from the top. For example, $M=3，p = \{3, 1, 2\}$, after performing one A-shuffle, from top to bottom it becomes $2, 3, 1$, i.e., card $1$ goes to position $3$, card $2$ goes to position $1$, card $3$ goes to position $2$. Now Bessie practices another method, called the B-shuffle. B-shuffle process: There is a stack of $N$（$M \le N \le 10 ^ 9$） cards labeled $1, 2, \cdots, N$, initially stacked in order from top to bottom $1$ to $N$. There is also an auxiliary stack used during shuffling, called the temporary pile, which starts empty. 1. Apply one A-shuffle to the top $M$ cards. 2. Move the top card to the top of the temporary pile, face down. 3. Repeat the previous two operations until the original pile is empty. During this process, when the original pile has fewer than $M$ cards remaining, do not perform the A-shuffle; instead, keep moving the top card to the temporary pile one by one. Given $N$, $M$ and the permutation $p$, there are $Q$（$1 \le Q \le \min(N, 5000)$） queries. After performing one B-shuffle, for each query, find the label of the card at position $q _ i$ in the temporary pile. Constraints: - $2 \le M \le 10 ^ 5$. - $M \le N \le 10 ^ 9$. - $1 \le Q \le \min(N, 5000)$. - $1 \le P[i] \le M$. - $1 \le q _ i \le N$. - $50\%$ of test cases have $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 \le P[i] \le 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 \le q_i \le N$).

* Lines 1..Q: On line $i$, print a single integer indicating the card at position $q_i$ from the top.

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, one for 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]. Translated by ChatGPT 5