Problem
Evan ha un numero preferito k e un array a
i di lunghezza n. Ora ti chiede di rispondere a m richieste.
Per ogni interrogazione data da una coppia di numeri l e r, è necessario trovare il numero di coppie di numeri interi i e j tali che l ≤ i ≤ j ≤ r e xor dei numeri a
i , a
i + 1, ..., a
j è k.< br />
Inserimento:
La prima riga contiene i numeri interi n, m e k (1 ≤ n, m ≤ 10
5, 0 ≤ k ≤ 10
6) — rispettivamente la lunghezza dell'array, il numero di richieste e il numero preferito di Evan.
La seconda riga contiene n numeri interi ai (0 ≤ a
i ≤ 10
6) — L'array di Evan.
Poi ci sono m righe. La riga i-esima contiene i numeri l
i e r
i (1 ≤ l
i ≤ r< sub>i ≤ n) che definisce l'i-esima query.
Uscita:
Stampa m righe, le risposte alle domande nell'ordine in cui appaiono nell'input.
Esempi:
| Input |
Uscita |
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 |