题目描述
已知一个长度为 n 的整数数列 a1,a2,…,an ,给定查询参数 l 、 r ,问在 al,al+1,…,ar 区间内,有多少子序列满足异或和等于 k 。也就是说,对于所有的 x,y(l≤x≤y≤r) ,满足 ax⊕ax+1⊕⋯⊕ay=k 的 x,y 有多少组。
输入格式
输入第一行为 3 个整数 n,m,k 。
第二行为空格分开的 n 个整数,即 a1,a2,…,an 。
接下来 m 行,每行两个整数 lj,rj ,代表一次查询。
输出格式
输出共 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≤n,m≤1000 。
对于 100% 的数据, 1≤n,m≤105,0≤k,ai≤105,1≤lj≤rj≤n 。