Étant donné une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ et un entier $K$. Écrivez un programme pour traiter les requêtes suivantes :

• l r : afficher le nombre de paires $(i, j)$ telles que $l \le i \le j \le r$ et le XOR de $A_i, A_{i+1}, \ldots, A_j$ égale $K$.

Entrée

La première ligne contient deux entiers $N$ $(1 \le N \le 100{,}000)$ et $K$ $(0 \le K \le 1{,}000{,}000)$.

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$. $(0 \le A_i \le 1{,}000{,}000)$

La troisième ligne contient un entier $M$ $(1 \le M \le 100{,}000)$, le nombre de requêtes.

Les $M$ lignes suivantes contiennent chacune deux entiers $l, r$, représentant une requête. $(1 \le l \le r \le N)$

Sortie

Pour chaque requête, afficher une ligne contenant un seul entier, la réponse.

Exemples

Entrée 1

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

Sortie 1

7
0

Entrée 2

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

Sortie 2

9
4
4