← 返回题目列表

Codeforces · 617/E

E. XOR 和最喜欢的号码

中文机器翻译题面 查看原题

Bob 有一个最喜欢的数字 k 和长度为 n 的 ai。现在他要求你回答 m 个问题。每个查询由一对 li 和 ri 给出,并要求您计算整数对 i 和 j 的数量,使得 l ≤ i ≤ j ≤ r 且数字 ai、ai + 1、...、aj 的异或等于 k。

输入

输入的第一行包含整数 n、m 和 k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000)——分别是数组的长度、查询的数量和 Bob 最喜欢的数字。

第二行包含 n 个整数 ai (0 ≤ ai ≤ 1 000 000) — Bob 的数组。

接下来是 m 行。第 i 行包含整数 li 和 ri (1 ≤ li ≤ ri ≤ n) — 第 i 个查询的参数。

输出

打印 m 行,按照查询在输入中出现的顺序回答查询。

示例

输入 #1

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

输出 #1

7
0

输入 #2

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

输出 #2

9
4
4

注意

在第一个样本中,第一个查询的合适 i 和 j 对为:(1, 2)、(1, 4)、(1, 5)、(2, 3)、(3, 6)、(5, 6)、(6, 6)。这些对中没有一个适合第二个查询。

在第二个样本中,对于奇数长度的所有子数组,异或等于 1。