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。