# Practice on Toph

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

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

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

For each query, print a line containing the answer to that query.

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 |

0% Solution Ratio

Login to submit

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