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*$.

Input

The first line of the input contains integers $*n*$, $*m*$ and $*k*$ ($1 ≤ *n*, *m* ≤ 100 000$, $0 ≤ *k* ≤ 1 000 000$) — 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*} ≤ 1 000 000$) — 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.

Output

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

Note

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.