给$n$个数字$a_1, a_2, \dots, a_n$。

你要回答$m$个询问，每次给定两个数$x, k$，询问$a_1~\mathrm{xor}~x, a_2~\mathrm{xor}~x, \dots, a_n~\mathrm{xor}~x$中从小到大排序中第$k$小的元素。

输入格式

第一行包含两个整数$n, m$。

第二行包含$n$个整数$a_1, a_2, \dots, a_n$。

接下来$m$行，每行两个数$x, k(1\leq k\leq n)$，表示一组询问。

输出格式

一共$m$行，每行一个整数，表示上面数字里面的第$k$小。

样例输入

5 5
11 10 6 4 14
15 1
11 4
3 5
6 1
9 1

样例输出

1
13
13
0
2

数据规模

对于$100\%$的数据，保证$1\leq n, m \leq 2\times 10^5, 0\leq a_i, x\leq 2^{30}-1$。