Es la semana de exámenes finales del último año de Busy Beaver, y acaba de recordar la lista de actividades obligatorias que recibió durante la orientación de primer año para completar antes de graduarse.
Se te da un arreglo de $N$ números $a_1, \ldots, a_N$, donde $a_i$ representa la alegría de completar la $i$-ésima actividad.
Debido a su tiempo limitado en el MIT, ha decidido completar solo un subsegmento contiguo de estas actividades. Además, para aprovecharlo al máximo, el subsegmento debe contener al menos dos actividades.
Mientras procrastinaba durante la preparación de sus exámenes finales, ideó una forma sofisticada de calificar un subsegmento. La puntuación del subsegmento desde el índice $l$ hasta el $r$ es el XOR mínimo de dos actividades distintas. Formalmente, el subsegmento desde el índice $l$ hasta el $r$ tiene una puntuación de $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$.
El número favorito de Busy Beaver es $K$, por lo que le gustaría calcular la cantidad de subsegmentos con puntuación $K$. ¿Puedes ayudarlo?
Entrada
La primera línea contiene dos enteros $N$ y $K$ ($2 \le N \le 10^5$, $0 \le K < 2^{30}$).
La segunda línea contiene $N$ enteros separados por espacios $a_1, \dots, a_N$ ($1 \le a_i < 2^{30}$).
Salida
Imprime un único entero: la cantidad de subsegmentos contiguos de tamaño al menos dos con puntuación $K$.
Puntuación
- ($15$ puntos) $N \leq 5000$.
- ($10$ puntos) $K = 0$.
- ($25$ puntos) El arreglo $a$ está ordenado de forma no decreciente ($a_{1} \leq \ldots \leq a_{N}$).
- ($50$ puntos) Sin restricciones adicionales.
Ejemplos
Entrada 1
5 2 1 3 1 4 5
Salida 1
3
Nota
Hay tres subsegmentos que deben contarse:
- $l = 1, r = 2$.
- $l = 2, r = 3$.
- $l = 2, r = 4$.