XOR and Favorite Number

题意翻译

- 给定一个长度为 $n$ 的序列 $a$，然后再给一个数字 $k$，再给出 $m$ 组询问，每组询问给出一个区间，求这个区间里面有多少个子区间的异或值为 $k$。 - $1 \le n,m \le 10 ^ 5$，$0 \le k,a_i \le 10^6$，$1 \le l_i \le r_i \le n$。 Translated by @char32_t，Reformed by @[明依](https://www.luogu.com.cn/user/155826)。

题目描述

Bob has a favorite number $ k $ and $ a_{i} $ of length $ n $ . Now he asks you to answer $ m $ queries. Each query is given by a pair $ l_{i} $ and $ r_{i} $ and asks you to count the number of pairs of integers $ i $ and $ j $ , such that $ l<=i<=j<=r $ and the xor of the numbers $ a_{i},a_{i+1},...,a_{j} $ is equal to $ k $ .

输入输出格式

输入格式

The first line of the input contains integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m<=100000 $ , $ 0<=k<=1000000 $ ) — the length of the array, the number of queries and Bob's favorite number respectively. The second line contains $ n $ integers $ a_{i} $ ( $ 0<=a_{i}<=1000000 $ ) — Bob's array. Then $ m $ lines follow. The $ i $ -th line contains integers $ l_{i} $ and $ r_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) — the parameters of the $ i $ -th query.

输出格式

Print $ m $ lines, answer the queries in the order they appear in the input.

输入输出样例

输入样例 #1

6 2 3
1 2 1 1 0 3
1 6
3 5

输出样例 #1

7
0

输入样例 #2

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

输出样例 #2

9
4
4

说明

In the first sample the suitable pairs of $ i $ and $ j $ for the first query are: ( $ 1 $ , $ 2 $ ), ( $ 1 $ , $ 4 $ ), ( $ 1 $ , $ 5 $ ), ( $ 2 $ , $ 3 $ ), ( $ 3 $ , $ 6 $ ), ( $ 5 $ , $ 6 $ ), ( $ 6 $ , $ 6 $ ). Not a single of these pairs is suitable for the second query. In the second sample xor equals $ 1 $ for all subarrays of an odd length.