У Эвана есть любимое число k и массив a
i длины n. Теперь он просит вас ответить на m запросов.
Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a
i, a
i + 1, ..., a
j равен k.
Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10
5, 0 ≤ k ≤ 10
6) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a
i ≤ 10
6) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l
i и r
i (1 ≤ l
i ≤ r
i ≤ 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 |