HeRock made an infinite array shuffler, which he thinks nobody can hack. The machine takes an infinite array, the operator gives it a key then it shuffles the array using that key. Now, he'll tell you the mechanism and the secret key. Can you hack the machine?
Shuffler Mechanism:
The shuffler has a secret key $P$ of $n$ distinct integers. It is guaranteed that $P$ has $0$ as one of its elements and the elements are sorted in ascending order. The shuffler has an array $G$ of infinite length. $G$ initially contains all integers from $0$ to infinity. The $0^{th}$ element is $0$, $1^{st}$ element is $1$, $2^{nd}$ element is $2$, and so on. It has another array $S$, which stores the shuffled array. Initially, $S$ is empty.
The machine does the following operations an infinite number of times:
Take all the elements at index
$P_i$(for each$i$in range$[0,n-1]$) from array$G$, put them in array$S$sequentially. All the elements taken away creates some empty spaces in array$G$.Shrink the array
$G$. That is if there is any empty position, fill it up with the element of the next non-empty position. Note that it'll create an empty position from where you have taken the element.
After repeating the operations an infinite number of times, the array $S$ is the infinite shuffled array.
Examples
If the key was 0, 1 then the shuffled array would look like
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, . . .
If the key was 0, 2 then the shuffled array would look like
0, 2, 1, 4, 3, 6, 5, 8, 7, 10, . . .
If the key was 0, 3, 4 then the shuffled array would look like
0, 3, 4, 1, 6, 7, 2, 9, 10, 5, . . .
To test whether you have successfully hacked the machine or not, HeRock will ask you $Q$ questions. On each question he will give you an integer $x$, You have to tell the element at index $x$ in array $S$. That means you need to print $S[x]$.
Input
Input starts with two integers $n$ and $Q (0 < n, Q \leq 10^5)$.
Next line contains $n$ integers, the elements of $P (0 \leq P_i \leq 10^{12})$.
The next $Q$ lines contains one integer each, the index $x (0 \leq x \leq 10^{12})$ for that query.
Output
For each query, print a line containing the answer to that query.
Samples
| Input | Output |
|---|---|
2 10 0 2 0 1 2 3 4 5 6 7 8 9 | 0 2 1 4 3 6 5 8 7 10 |
| Input | Output |
|---|---|
3 8 0 3 4 0 1 2 3 4 5 6 7 | 0 3 4 1 6 7 2 9 |
