Problems
XOR
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 ≤ **
a[i] ≤ 106
) — имеющийся у Назара массив. Дальше идут m строк. В i-й строке записаны числа li
и ri
(1 ≤ li, ri
≤ n), определяющие i-й запрос.
Выходные данные
Выведите m строк, ответы на запросы.
Input example #1
6 2 3 1 2 1 1 0 3 1 6 3 5
Output example #1
7 0
Input example #2
5 3 1 1 1 1 1 1 1 5 2 4 1 3
Output example #2
9 4 4