给定长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$ 和整数 $K$。编写一个程序处理以下查询：

• l r：输出满足 $l \le i \le j \le r$ 且 $A_i, A_{i+1}, \ldots, A_j$ 的 XOR 值等于 $K$ 的 $(i, j)$ 对数。

输入格式

第一行包含两个整数 $N$ $(1 \le N \le 100{,}000)$ 和 $K$ $(0 \le K \le 1{,}000{,}000)$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。$(0 \le A_i \le 1{,}000{,}000)$

第三行包含一个整数 $M$ $(1 \le M \le 100{,}000)$，表示查询的数量。

接下来 $M$ 行，每行包含两个整数 $l, r$，表示一个查询。$(1 \le l \le r \le N)$

输出格式

对于每个查询，输出一行，包含一个整数，表示答案。

样例

输入 1

6 3
1 2 1 1 0 3
2
1 6
3 5

输出 1

7
0

输入 2

5 1
1 1 1 1 1
3
1 5
2 4
1 3

输出 2

9
4
4