给定 $n$ 个整数 $x_1,x_2,\ldots,x_n$。现有 $q$ 次询问，每次询问给定一个函数 $f(x)=(a\oplus x)-b$，请判断是否存在 $1\le i<n$ 满足 $f(x_i)\cdot f(x_{i+1})\le 0$，如果存在请输出一个满足条件的 $i$，否则输出 $-1$。

$a\oplus b$ 表示 $a$ 异或 $b$。

Input

第一行两个整数 $n,q$（$2\le n\le 3\cdot 10^5$，$1\le q\le 3\cdot 10^5$）。

第二行 $n$ 个整数 $x_1,x_2,\ldots,x_n$（$0\le x_i\le 10^9$）。

接下来 $q$ 行，每行两个整数 $a,b$（$0\le a,b\le 10^9$）。

Output

输出 $q$ 行，表示对每个询问的回答。

5 6
3 5 1 2 4
0 2
1 1
2 3
3 2
4 2
5 8

2
3
2
1
4
-1