Problem
Evan 有一个最喜欢的数字 k 和一个长度为 n 的数组 a
i。现在它要求你回答 m 个请求。
对于由一对数字 l 和 r 给出的每个查询，需要找到整数对 i 和 j 的数量，使得 l ≤ i ≤ j ≤ r 和 xor数字 a
i , a
i + 1, ..., a
j 是 k。< br />
输入：
第一行包含整数 n、m 和 k (1 ≤ n, m ≤ 10
5, 0 ≤ k ≤ 10
6) ——数组的长度，请求的数量，以及 Evan 最喜欢的数字。
第二行包含n个整数ai (0 ≤ a
i ≤ 10
6) —埃文的阵列。
然后有m行。第 i 行包含数字 l
i 和 r
i (1 ≤ l
i ≤ r< sub>i ≤ n) 定义第 i 个查询。
输出：
打印 m 行，问题的答案按照它们在输入中出现的顺序排列。
示例：
<正文>
| 输入 |
输出 |
6 2 3
1 2 1 1 0 3
16
3 5
| 7
0 |
5 3 1
1 1 1 1 1
15
24
1 3
| 9
4
4 |