The Bessie Shuffle

Bessie is practicing her card tricks. She has already mastered the Bessie shuffle, a shuffle on $M$ cards ($2 \le M \le 100{,}000$) that rearranges them so the $i$-th card from the top becomes the $P_i$-th card from the top.

Now Bessie practices on a bigger deck. It holds $N$ cards ($M \le N \le 1{,}000{,}000{,}000$) labeled $1$ to $N$. She takes the top $M$ cards, performs the Bessie shuffle on them, and puts them back on top of the deck. She then removes the top card and places it face down. She repeats this, stacking each removed card on top of the ones she has already placed, until the deck is empty. Once fewer than $M$ cards are left she stops shuffling, but she keeps moving the top card onto the pile.

The deck starts sorted, with $1$ on top, $2$ next and $N$ on the bottom. Given the Bessie shuffle, answer $Q$ queries ($1 \le Q \le N$, $Q \le 5{,}000$): which card ends up at position $q_i$ from the top of the finished pile?

The first line contains $N$, $M$ and $Q$ separated by spaces.

Each of the next $M$ lines contains one integer. Line $i+1$ holds $P_i$, the position that the $i$-th card from the top moves to in the Bessie shuffle ($1 \le P_i \le M$). The values $P_1$ through $P_M$ use each of $1$ through $M$ exactly once.

Each of the next $Q$ lines contains one integer $q_i$, the $i$-th query ($1 \le q_i \le N$). It asks for the card at position $q_i$ from the top of the finished pile.

Print $Q$ lines. On line $i$, print the label of the card at position $q_i$ from the top of the finished pile.

In the first example Bessie has $5$ cards ordered $[1, 2, 3, 4, 5]$. Her shuffle works on $3$ cards and moves the top card of the window to the bottom. The deck changes like this:

• $[1, 2, 3, 4, 5] \to [2, 3, 1, 4, 5]$, then $2$ goes face down
• $[3, 1, 4, 5] \to [1, 4, 3, 5]$, then $1$ goes face down
• $[4, 3, 5] \to [3, 5, 4]$, then $3$ goes face down
• $[5, 4]$, then $5$ goes face down
• $[4]$, then $4$ goes face down

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