The Bessie Shuffle

Bessie is practicing her card tricks. She has already mastered the Bessie shuffle, a shuffle on $M$ cards that moves the $i$-th card from the top to position $P[i]$ from the top.

Now Bessie practices on a bigger deck. The deck holds $N$ cards labeled $1$ through $N$. She takes the top $M$ cards, performs the Bessie shuffle on them, and puts the shuffled cards back on top of the deck. She then removes the top card and places it face down. She repeats this until the deck runs out. Each card she removes goes on top of the cards she has already put down. Once fewer than $M$ cards are left she stops shuffling and only keeps moving the top card onto the pile.

The deck starts in sorted order with $1$ on top, $2$ next and $N$ at the bottom. Given the description of the Bessie shuffle, compute the label of the card that ends up at each of the positions $q_1, q_2, \dots, q_Q$ of the finished pile, counted from its top.

The first line contains $N$, $M$ and $Q$ separated by spaces ($2 \le M \le N \le 100{,}000$, $1 \le Q \le \min(N, 5{,}000)$).

Each of the next $M$ lines holds $P[i]$, the position that the $i$-th card from the top moves to during the Bessie shuffle ($1 \le P[i] \le M$). $P$ is a permutation of $1$ through $M$.

Each of the following $Q$ lines holds one query $q_i$ ($1 \le q_i \le N$).

Print $Q$ lines. Line $i$ holds the label of the card at position $q_i$ from the top of the finished pile.

Take five cards stacked as $[1, 2, 3, 4, 5]$ from the top, with a shuffle on three cards that sends the top card to the bottom. The process runs like this:

• $[1, 2, 3, 4, 5] \to [2, 3, 1, 4, 5]$, put $2$ face down
• $[3, 1, 4, 5] \to [1, 4, 3, 5]$, put $1$ face down
• $[4, 3, 5] \to [3, 5, 4]$, put $3$ face down
• $[5, 4]$, fewer than three cards remain, so put $5$ face down with no shuffle
• $[4]$, put $4$ face down

The finished pile reads $[4, 5, 3, 1, 2]$ from the top.