Module: Algoritmo Mo

Problem

Evan tiene un número favorito k y una matriz a_i de longitud n. Ahora te pide que respondas m solicitudes.

Para cada consulta dada por un par de números l y r, se requiere encontrar el número de pares de números enteros i y j tales que l ≤ i ≤ j ≤ r y xor de los números a_i , a_i + 1, ..., a_j es k.< br />
Entrada:
La primera línea contiene números enteros n, m y k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤  10 ⁶) — la longitud de la matriz, el número de solicitudes y el número favorito de Evan, respectivamente.
La segunda línea contiene n enteros ai (0 ≤ a_i ≤ 10⁶) — Matriz de Evan.
Luego hay m líneas. La i-ésima línea contiene los números l_i y r_i (1 ≤ l_i ≤ r< sub>i ≤ n) que define la i-ésima consulta.

Salida:
Imprime m líneas, las respuestas a las preguntas en el orden en que aparecen en la entrada.

Ejemplos:
 

Entrada	Salida
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