Description

Given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$, for a query with parameters $l, r$, ask how many subarrays within $a_l, a_{l+1}, \dots, a_r$ have xor-sum equal to $k$. That is, among all $x, y$ such that $(l \leq x \leq y \leq r)$, how many pairs $(x, y)$ satisfy $a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k$.

Input Format

The first line contains three integers $n, m, k$.

The second line contains $n$ integers separated by spaces, namely $a_1, a_2, \dots, a_n$.

Each of the next $m$ lines contains two integers $l_j$ and $r_j$, representing one query.

Output Format

Output $m$ lines, each corresponding to the answer for one query.

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

4
2
1
2
1

Hint

For $30\%$ of the testdata, $1 \leq n, m \leq 1000$.

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $0 \leq k, a_i \leq 10^5$, $1 \leq l_j \leq r_j \leq n$.

Translated by ChatGPT 5