D. Изменения массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На перемене Ваня зашел в класс и увидел на доске массив из $$$n$$$ целых неотрицательных $$$k$$$-битных чисел $$$a_1, a_2, \ldots, a_n$$$. Число $$$x$$$ называется $$$k$$$-битным, если $$$0 \leq x \leq 2^k - 1$$$.

Естественно, Ваня не удержался и стал менять числа, написанные на доске. Для того, чтобы никто ничего не заметил, Ваня разрешил себе сделать несколько следующих изменений: выбрать индекс массива $$$i$$$ ($$$1 \leq i \leq n$$$) и заменить число $$$a_i$$$ на число $$$\overline{a_i}$$$. Будем обозначать за $$$\overline{x}$$$ для $$$k$$$-битного числа $$$x$$$ такое $$$k$$$-битное число, что все его $$$k$$$ битов отличаются от соответствующих битов числа $$$x$$$.

Ване очень не нравится число $$$0$$$. Поэтому ему нравятся такие отрезки $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$), что $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ. Определите, какое максимальное количество таких отрезков он сможет получить, выполнив несколько (возможно, ноль) операций, описанных выше.

Входные данные

В первой строке входных данных находятся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq k \leq 30$$$).

В следующей строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2^k - 1$$$), разделённых пробелами — массив из $$$k$$$-битных чисел.

Выходные данные

Выведите одно целое число — максимальное возможное количество отрезков с побитовым исключающим ИЛИ, не равным $$$0$$$, которое можно получить, сделав несколько (возможно, $$$0$$$) операций, описанных в условии.

Примеры
Входные данные
3 2
1 3 0
Выходные данные
5
Входные данные
6 3
1 4 4 7 3 4
Выходные данные
19
Примечание

В первом тесте можно не делать операций, тогда мы получим, что у нас $$$5$$$ отрезков, которые нравятся Ване. Если сделать операцию с $$$i = 2$$$, то получится массив $$$[1, 0, 0]$$$, так как $$$\overline{3} = 0$$$ при $$$k = 2$$$. У такого массива будет $$$3$$$ подотрезка, которые нравятся Ване. Можно получить массив с $$$5$$$ подотрезками, которые нравятся Ване, если сделать операцию с $$$i = 3$$$ и операцию с $$$i = 2$$$. Тогда получится массив $$$[1, 0, 3]$$$. Можно доказать, что $$$6$$$ и более отрезков, которые будут нравиться Ване, получить невозможно.

Во втором тесте, чтобы получить $$$19$$$ подотрезков, которые нравятся Ване, можно сделать $$$4$$$ операции с $$$i = 3$$$, $$$i = 4$$$, $$$i = 5$$$ и $$$i = 6$$$. Получится массив $$$[1, 4, 3, 0, 4, 3]$$$.