# 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.