Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$ and an integer $K$. Write a program to process the following queries:

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

Input

The first line contains two integers $N$ $(1 \le N \le 100{,}000)$ and $K$ $(0 \le K \le 1{,}000{,}000)$.

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

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

The next $M$ lines each contain two integers $l, r$, representing a query. $(1 \le l \le r \le N)$

Output

For each query, output a line containing a single integer, the answer.

Examples

Input 1

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

Output 1

7
0

Input 2

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

Output 2

9
4
4