[CQOI2018] 异或序列

题目描述

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

输入输出格式

输入格式


输入文件第一行,为 $3$ 个整数 $n,m,k$。 第二行为空格分开的 $n$ 个整数,即 $a_1,a_2,..a_n$。 接下来 $m$ 行,每行两个整数 $l_j,r_j$,表示一次查询。

输出格式


输出文件共 $m$ 行,对应每个查询的计算结果。

输入输出样例

输入样例 #1

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

输出样例 #1

4
2
1
2
1

说明

对于 $30\%$ 的数据,$1 \leq n, m \leq 1000$。 对于 $100\%$ 的数据,$1 \leq n, m \leq 10^5$,$0 \leq k, a_i \leq 10^5$,$1 \leq l_j \leq r_j \leq n$。