E. Supersequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

An array $$$a$$$ is called a subsequence of an array $$$b$$$ if some elements can be removed from array $$$b$$$ (possibly all, possibly none) to obtain the array $$$a$$$.

You are given an array $$$a = [a_1, a_2, \dots, a_n]$$$. We call an array $$$b = [b_1, b_2, \dots, b_m]$$$ beautiful if:

  • $$$a$$$ is a subsequence of $$$b$$$;
  • for each $$$i$$$ from $$$1$$$ to $$$m-1$$$, the elements $$$b_i$$$ and $$$b_{i+1}$$$ differ by exactly $$$1$$$ (that is, $$$|b_i - b_{i+1}| = 1$$$);
  • among all arrays that satisfy these two requirements, the length of $$$b$$$ is minimum.

You have to process $$$q$$$ queries. In the $$$i$$$-th query, a single integer $$$x_i$$$ is given. Your task is as follows:

  • if $$$x_i$$$ is greater than the minimum possible number of elements in a beautiful array, print $$$-1$$$;
  • otherwise, if the same number occupies position $$$x_i$$$ in all beautiful arrays, print that number;
  • otherwise, print $$$0$$$.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The third line contains $$$q$$$ integers $$$x_1, x_2, \dots, x_q$$$ ($$$1 \le x_i \le 10^{18}$$$).

Output

For each query, print a single integer — the answer to it.

Example
Input
5 16
4 1 1 5 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Output
4 3 2 1 0 1 2 3 4 5 6 7 8 9 -1 -1