[CQOI2018]异或序列

题目描述

已知一个长度为n的整数数列$a_1,a_2,...,a_n$,给定查询参数l、r,问在$a_l,a_{l+1},...,a_r$区间内,有多少子序列满足异或和等于k。也就是说,对于所有的x,y (I ≤ x ≤ y ≤ r),能够满足$a_x \bigoplus a_{x+1} \bigoplus ... \bigoplus 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 ≤ n, m ≤ 1000$ 对于100%的数据,$1 ≤ n, m ≤ 10^5, 0 ≤ k, a_i ≤ 10^5,1 ≤ l_j ≤ r_j ≤ n$