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

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

Ограничение по времени Ограничение по памяти
1 секунда 64 мегабайта

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

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

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

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

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

Примеры

Вход

5 0
1 2 3 4 5

Выход

15

Вход

3 3
1 2 3

Выход

2