У Назара есть любимое число 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 целых чисел a[i] (0 ≤ **
a[i] ≤ 10^6
) — имеющийся у Назара массив. Дальше идут m строк. В i-й строке записаны числа l[i]
и r[i]
(1 ≤ l[i], r[i]
≤ n), определяющие i-й запрос.
Выведите m строк, ответы на запросы.