C'est la semaine des examens finaux de la dernière année de Busy Beaver, et il vient de se souvenir de la liste des activités incontournables à accomplir avant l'obtention de son diplôme, qu'il avait reçue lors de l'orientation des étudiants de première année.
On vous donne un tableau de $N$ nombres $a_1, \ldots, a_N$, où $a_i$ représente la joie procurée par l'accomplissement de la $i^\text{ème}$ activité.
En raison du temps limité dont il dispose au MIT, il a décidé de ne réaliser qu'un sous-segment contigu de ces activités. De plus, pour en tirer le meilleur parti, le sous-segment doit contenir au moins deux activités.
Alors qu'il procrastinait pendant ses révisions pour ses examens finaux, il a imaginé une méthode sophistiquée pour noter un sous-segment. Le score du sous-segment allant de l'indice $l$ à $r$ est le XOR minimum de deux activités distinctes. Formellement, le sous-segment de l'indice $l$ à $r$ a un score de $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$.
Le nombre préféré de Busy Beaver est $K$, il aimerait donc calculer le nombre de sous-segments ayant un score égal à $K$. Pouvez-vous l'aider ?
Entrée
La première ligne contient deux entiers $N$ et $K$ ($2 \le N \le 10^5$, $0 \le K < 2^{30}$).
La deuxième ligne contient $N$ entiers séparés par des espaces $a_1, \dots, a_N$ ($1 \le a_i < 2^{30}$).
Sortie
Affichez un seul entier : le nombre de sous-segments contigus de taille au moins deux ayant un score égal à $K$.
Sous-tâches
- ($15$ points) $N \leq 5000$.
- ($10$ points) $K = 0$.
- ($25$ points) Le tableau $a$ est trié par ordre non décroissant ($a_{1} \leq \ldots \leq a_{N}$).
- ($50$ points) Aucune contrainte supplémentaire.
Exemples
Entrée 1
5 2 1 3 1 4 5
Sortie 1
3
Remarque
Il y a trois sous-segments qui doivent être comptés :
- $l = 1, r = 2$.
- $l = 2, r = 3$.
- $l = 2, r = 4$.