Модуль: Алгоритм Мо


Задача

3 /4


XOR и любимое число


Задача

У Эвана есть любимое число k и массив ai длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел ai, ai + 1, ..., aj равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 106) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 106) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа li и ri (1 ≤ li ≤ ri ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

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

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w642
Комментарий учителя