给定 $n$ 个整数 $x_1, x_2, \dots, 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$ 的按位异或运算。

输入格式

第一行包含两个整数 $n, q$ ($2 \le n \le 3 \cdot 10^5$, $1 \le q \le 3 \cdot 10^5$)。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^9$)。

接下来 $q$ 行，每行包含两个整数 $a, b$ ($0 \le a, b \le 10^9$)。

输出格式

输出 $q$ 行，表示每次查询的答案。

样例

样例输入 1

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

样例输出 1

2
3
2
1
4
-1