Олимпиадный тренинг

Задача . E. 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 ≤ 100 000, 0 ≤ k ≤ 1 000 000) — длина массива, количество запросов и любимое число Васи соответственно.

Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 1 000 000) — имеющийся у Васи массив.

Дальше идут m строк. В i-й строке записаны числа li и ri (1 ≤ li ≤ ri ≤ n), определяющие i-й запрос.

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

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

Примечание

В первом примере подходят пары чисел (1, 2), (1, 4), (1, 5), (2, 3), (3, 6), (5, 6), (6, 6). Ни одна из этих пар не подходит для второго запроса.

Во втором примере xor равен 1 для всех подмассивов нечётной длины.


Примеры
№Входные данныеВыходные данные
1
6 2 3
1 2 1 1 0 3
1 6
3 5
7
0
2
5 3 1
1 1 1 1 1
1 5
2 4
1 3
9
4
4
Статистика успешных решений по компиляторам
 Кол-во
С++5