题目描述

给你一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

接下来有 $q$ 次询问，每次询问给你两个整数 $x$ 和 $k$，你需要判断数列 $a$ 中存在多少个元素与 $x$ 的异或和 $\le k$？

也就是说，你需要统计存在多少个下标 $i$ 满足 $1 \le i \le n$ 且 $a_i \oplus x \le k$。这里，$\oplus$ 是异或符号。

输入格式

第一行，两个整数 $n$ 和 $q$，以一个空格分隔，分别表示数列长度以及询问次数。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

接下来 $q$ 行，每行包含两个整数 $x$ 和 $k$，以空格分隔，表示一次询问。

输出格式

对于每次询问，输出一行，包含一个整数，表示答案（即存在多少个 $a_i$ 满足 $a_i \oplus x \le k$）。

样例

5 2
1 2 3 4 5
2 3
5 3

3
2

12 10
8 2 3 7 6 15 20 13 5 12 1 10
7 5
3 11
8 15
6 20
8 10
5 15
8 10
7 16
13 0
7 11

5
8
11
12
7
11
7
11
1
9

说明/提示

样例 1 解释

第一次询问，$x = 2$，$k = 3$

• $a_1 = 1, 1 \oplus 2 = 3 \le 3$ 满足条件；
• $a_2 = 2, 2 \oplus 2 = 0 \le 3$ 满足条件；
• $a_3 = 3, 3 \oplus 2 = 1 \le 3$ 满足条件；
• $a_4 = 4, 4 \oplus 2 = 6 \gt 3$ 不满足条件；
• $a_5 = 5, 5 \oplus 2 = 7 \gt 3$ 不满足条件。

第二次询问，$x = 5$，$k = 3$

• $a_1 = 1, 1 \oplus 5 = 4 \gt 3$ 不满足条件；
• $a_2 = 2, 2 \oplus 5 = 7 \gt 3$ 不满足条件；
• $a_3 = 3, 3 \oplus 5 = 6 \gt 3$ 不满足条件；
• $a_4 = 4, 4 \oplus 5 = 1 \le 3$ 满足条件；
• $a_5 = 5, 5 \oplus 5 = 0 \le 3$ 满足条件。

数据规模与约定

• 对于 $60\%$ 的数据，$n,q \le 2000$，$a_i, x, k \lt 2^{10}$
• 对于 $100\%$ 的数据，$1 \le n,q \le 2 \cdot 10^5$，$0 \le a_i, x, k \lt 2^{20}$