#5301. [Cqoi2018]异或序列

内存限制:512 MiB 时间限制:10 Sec

题目描述

已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ,给定查询参数 l、r ,问在 [l,r] 区间内,有多少连续子
序列满足异或和等于 k 。
也就是说,对于所有的 x,y (l≤x≤y≤r),能够满足a[x]^a[x+1]^…^a[y]=k的x,y有多少组。

输入格式

输入文件第一行,为3个整数n,m,k。
第二行为空格分开的n个整数,即ai,a2,….an。
接下来m行,每行两个整数lj,rj,表示一次查询。
1≤n,m≤105,O≤k,ai≤105,1≤lj≤rj≤n

输出格式

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

样例

样例输入


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

样例输出


			
4
2
1
2
1

数据范围与提示