Problem
Evan tem um número favorito k e um array a
i de comprimento n. Agora ele pede para você responder a m solicitações.
Para cada consulta dada por um par de números l e r, é necessário encontrar o número de pares de inteiros i e j tais que l ≤ i ≤ j ≤ r e xor de números a
i , a
i + 1, ..., a
j é k.< br />
Entrada:
A primeira linha contém inteiros n, m e k (1 ≤ n, m ≤ 10
5, 0 ≤ k ≤ 10
6) — o comprimento da matriz, o número de solicitações e o número favorito de Evan, respectivamente.
A segunda linha contém n inteiros ai (0 ≤ a
i ≤ 10
6) — Matriz de Evan.
Então há m linhas. A i-ésima linha contém os números l
i e r
i (1 ≤ l
i ≤ r< sub>i ≤ n) definindo a i-ésima consulta.
Saída:
Imprima m linhas, as respostas às perguntas na ordem em que aparecem na entrada.
Exemplos:
| Entrada |
Saída |
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 |