E. XOR и любимое число
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Васи есть любимое число 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 строк, ответы на запросы в порядке их появления во входных данных.

Примеры
Входные данные
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
Примечание

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

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