题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 以及一个整数 $k$。

你需要依次回答 $m$ 次询问，每次询问给你两个整数 $l$ 和 $r$，你需要回答出区间 $[l, r]$ 存在多少子区间的异或和为 $k$。即：你需要判断存在多少对下标对 $(i, j)$ 满足 $l \le i \le j \le r$ 且 $a_i \oplus a_{i+1} \oplus \ldots \oplus a_j = k$。（这里 $\oplus$ 表示异或符号）

输入格式

第一行，三个整数 $n$、$m$ 和 $k$（$1 \le n,m \le 10^5, 0 \le k \le 10^6$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^6)$。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一次询问（$1 \le l \le r \le n$）。

输出格式

对于每次询问，输出一个整数，表示区间 $[l, r]$ 范围内存在多少个子区间的异或和为 $k$。

样例

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

7
0

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

9
4
4

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 10, k, a_i \le 100$
• 对于 $60\%$ 的数据，$n,m \le 1000, k, a_i \le 10000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5, 0 \le k, a_i \le 10^6, 1 \le l \le r \le n$