Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Infinite Shuffler

By curly_braces · Limits 2s, 256 MB

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:

  1. 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$.

  2. 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

InputOutput
2 10
0 2
0
1
2
3
4
5
6
7
8
9
0
2
1
4
3
6
5
8
7
10
InputOutput
3 8
0 3 4
0
1
2
3
4
5
6
7
0
3
4
1
6
7
2
9

    Discussion

    Statistics


    0% Solution Ratio

    Submit

    Login to submit

    Editorial

    Consider a query for x. From the value of x we can derive at which cycle of operations it occured an...