Problem
Evan a un nombre favori k et un tableau a
i de longueur n. Maintenant, il vous demande de répondre à m requêtes.
Pour chaque requête donnée par un couple de nombres l et r, il faut trouver le nombre de couples d'entiers i et j tels que l ≤ i ≤ j ≤ r et xor des nombres a
i , a
i + 1, ..., a
j est k.< br />
Saisie :
La première ligne contient des entiers n, m et k (1 ≤ n, m ≤ 10
5, 0 ≤ k ≤ 10
6) &mdash ; la longueur du tableau, le nombre de requêtes et le numéro préféré d'Evan, respectivement.
La deuxième ligne contient n entiers ai (0 ≤ a
i ≤ 10
6) — Le tableau d'Evan.
Ensuite, il y a m lignes. La ième ligne contient les nombres l
i et r
i (1 ≤ l
i ≤ r< sub>i ≤ n) définissant la ième requête.
Sortie :
Imprimer m lignes, les réponses aux questions dans l'ordre où elles apparaissent dans l'entrée.
Exemples :
| Entrée |
Sortie |
6 2 3
1 2 1 1 0 3
16
3 5
| 7
0 |
5 3 1
1 1 1 1 1
15
24
1 3
| 9
4
4 |