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$.