Sequence and Queries 11

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ and an integer $K$. Write a program that processes the following query.

• l r: print the number of pairs $(i, j)$ with $l \le i \le j \le r$ such that the XOR of $A_i, A_{i+1}, \ldots, A_j$ is $K$.

The first line contains the length of the sequence $N$ ($1 \le N \le 100{,}000$) and $K$ ($0 \le K \le 1{,}000{,}000$).

The second line contains $A_1, A_2, \ldots, A_N$ ($0 \le A_i \le 1{,}000{,}000$).

The third line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

Each of the next $M$ lines contains one query $l$, $r$ ($1 \le l \le r \le N$).

For each query, print the answer on its own line.