Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$ y un entero $K$. Escribe un programa para procesar las siguientes consultas:

• l r: imprime la cantidad de pares $(i, j)$ tales que $l \le i \le j \le r$ y el XOR de $A_i, A_{i+1}, \ldots, A_j$ es igual a $K$.

Entrada

La primera línea contiene dos enteros $N$ $(1 \le N \le 100\,000)$ y $K$ $(0 \le K \le 1\,000\,000)$.

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_N$. $(0 \le A_i \le 1\,000\,000)$

La tercera línea contiene un entero $M$ $(1 \le M \le 100\,000)$, la cantidad de consultas.

Las siguientes $M$ líneas contienen cada una dos enteros $l, r$, representando una consulta. $(1 \le l \le r \le N)$

Salida

Para cada consulta, imprime una línea que contenga un solo entero, la respuesta.

Ejemplos

Entrada 1

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

Salida 1

7
0

Entrada 2

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

Salida 2

9
4
4