Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

(XOR-ға тағы бір есеп)

Ограничение по времени:

1 секунд

Ограничение по памяти:

64 мегабайт

Сізге $n$ бүтін саннан тұратын $A$ сандар реті берілген. Берілген $X$ саны бойынша келесі шарт орындалатын $1 \le l \le r \le n$ қос сандардың санын табыңыз: $X \le A[l]\ xor\ A[l + 1]\ xor\ ...\ xor\ A[r]$. $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

Замечание

1ші есеп бөлімі, 31 ұпай $1 \le n \le 1000$ 2ші есеп бөлімі, 69 ұпай $1 \le n \le 100000$

Комментарий/решение

Это задача решается с помощью цифрового бора