题目描述
已知一个长度为 (n) 的整数数列 (a_1, a_2, \dots, a_n)，给定查询参数 (l)、(r)，问在 (a_l, a_{l+1}, \dots, a_r) 区间内，有多少子序列满足异或和等于 (k)。也就是说，对于所有的 (x, y)（(l \le x \le y \le r)），满足 (a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k) 的 (x, y) 有多少组。

输入格式
输入第一行为 3 个整数 (n, m, k)。
第二行为空格分开的 (n) 个整数，即 (a_1, a_2, \dots, a_n)。
接下来 (m) 行，每行两个整数 (l_j, r_j)，代表一次查询。

输出格式
输出共 (m) 行，对应每个查询的计算结果。

样例
输入：

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

输出：

4
2
1
2
1

数据范围与提示
对于 (30%) 的数据，(1 \le n, m \le 1000)。
对于 (100%) 的数据，(1 \le n, m \le 10^5)，(0 \le k, a_i \le 10^5)，(1 \le l_j \le r_j \le n)。