G. Function Query
time limit per test
2 seconds
memory limit per test
256 MB
input
standard input
output
standard output

Given $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$. There are $$$q$$$ queries, each query gives a function $$$f(x)=(a\oplus x)-b$$$, please determine if there exists $$$1\le i \lt n$$$ such that $$$f(x_i)\cdot f(x_{i+1})\le 0$$$, if so, output a satisfying $$$i$$$, otherwise output $$$-1$$$.

$$$a\oplus b$$$ represents the bitwise XOR operation between $$$a$$$ and $$$b$$$.

Input

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

The second line contains $$$n$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$0\le x_i\le 10^9$$$).

Following are $$$q$$$ lines, each line contains two integers $$$a,b$$$ ($$$0\le a,b\le 10^9$$$).

Output

Output $$$q$$$ lines, representing the answer for each query.

Example
Input
5 6
3 5 1 2 4
0 2
1 1
2 3
3 2
4 2
5 8
Output
2
3
2
1
4
-1