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