Республиканская олимпиада по информатике 2014 года за 9 класс | Казахстанские олимпиады

Задача D. Еще одна задача на XOR

Вам дан массив $A$ из $n$ неотрицательных целых чисел, посчитайте количество пар чисел $1 \le l \le r \le n$, таких что $X \le A[l]\ xor\ A[l + 1]\ xor\ ...\ xor\ A[r]$, для некоторого заданного целого числа $X$. $xor$ — операция побитового сложения (в двоичной системе) по модулю два. Результатом этой операции является единица только в том случае, если биты операндов различны. Пример: $10_{10}\ xor\ 23_{10}\ =\ 29_{10}$, $1010_2\ xor\ 10111_2\ =\ 11101_2$, здесь записано одно и то же равенство в десятичной, а затем в двоичной системе счисления.

Формат входного файла

В первой строке входных данных содержится два целых числа, разделенных пробелом $n$ и $0 \le X \le 10^9$. В следующей строке заданы $n$ целых чисел разделенных пробелами. Каждое из этих чисел не превосходит $10^9$.

Формат выходного файла

Единственное число, ответ на задачу.

Примеры

Вход

5 0
1 2 3 4 5

Выход

15

Вход

3 3
1 2 3

Выход

2