Next Smaller Element

You will be given a long array $ar$. The length of the array is $n^{100}$ where $n$ will be given. The first $n$ elements $ar[1],ar[2],...,ar[n]$ of the array will be given as input. The rest of the elements will be calculated as $ar[i] = ar[((i - 1)\mod n) + 1] + ((i - 1) / n)$ where $n < i \le n^{100}$.

Let's say for $n = 3$, the first $n$ elements are $[3, 6, 1]$, then the rest of the elements of the array will be $[4, 7, 2, 5, 8, 3, 6, 9, 4]$ and so on.

You will also be given $q$ queries. In each query, you will be given a number $x$. You need to print the next smaller element after position $x$. In other words, you need to find a number $ar[j]$ where $ar[j] < ar[x] \text{ and } j > x$ and $j$ is the smallest possible. If there is no such number exists, print $-1$.

Input

The first line of input will have two integers $n\text{ } (2 ≤ n ≤ 3\times 10^{5})$ and $q\text{ }(1 \le q \le 10^5)$.

In the next line, the first $n$ elements of the array will be given where $1 ≤ ar[i] ≤ 3 \times 10^5$ for every $1 ≤ i ≤ n$.

Each of the following $q$ lines will have one integer $x\text{ }(1 \le x \le 10^{12})$.

Output

For each query, print the desired number as described in the problem statement.

Sample

3 5
3 6 1
1
2
3
4
5

1
1
-1
2
2