Наступила последняя неделя перед окончанием университета для Busy Beaver, и он только что вспомнил о списке обязательных дел, которые нужно выполнить до выпуска, полученном еще на первом курсе.
Дан массив из $N$ чисел $a_1, \ldots, a_N$, где $a_i$ представляет собой радость от выполнения $i$-го дела.
Из-за ограниченного времени он решил выполнить только непрерывный подотрезок этих дел. Кроме того, чтобы получить от этого максимум пользы, подотрезок должен содержать как минимум два дела.
Откладывая подготовку к экзаменам, он придумал сложный способ оценки подотрезка. Оценка подотрезка с индекса $l$ по $r$ — это минимальное значение XOR двух различных дел в нем. Формально, подотрезок с индекса $l$ по $r$ имеет оценку $\min\limits_{l \leq i < j \leq r} a_i \oplus a_j$.
Любимое число Busy Beaver — $K$, поэтому он хочет вычислить количество подотрезков с оценкой $K$. Можете ли вы ему помочь?
Входные данные
Первая строка содержит два целых числа $N$ и $K$ ($2 \le N \le 10^5$, $0 \le K < 2^{30}$).
Вторая строка содержит $N$ целых чисел $a_1, \dots, a_N$, разделенных пробелами ($1 \le a_i < 2^{30}$).
Выходные данные
Выведите одно целое число: количество непрерывных подотрезков размера как минимум два, оценка которых равна $K$.
Подзадачи
| Баллы | Ограничения |
|---|---|
| 15 | $N \leq 5000$ |
| 10 | $K = 0$ |
| 25 | Массив $a$ отсортирован в неубывающем порядке ($a_{1} \leq \ldots \leq a_{N}$) |
| 50 | Без дополнительных ограничений |
Примеры
Входные данные 1
5 2 1 3 1 4 5
Выходные данные 1
3
Примечание
Существует три подотрезка, которые следует учесть:
- $l = 1, r = 2$.
- $l = 2, r = 3$.
- $l = 2, r = 4$.