eolymp
bolt
Try our new interface for solving problems

XOR

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

У Назара есть любимое число k и массив a[i] длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor (обозначается знаком ^ в С++) чисел a[i]; a[i+1]; …; a[j] равен k.

Giriş verilənləri

В первой строке даны целые числа 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-й запрос.

Çıxış verilənləri

Выведите m строк, ответы на запросы.

Nümunə

Giriş verilənləri #1
6 2 3
1 2 1 1 0 3
1 6
3 5
Çıxış verilənləri #1
7
0
Giriş verilənləri #2
5 3 1
1 1 1 1 1
1 5
2 4
1 3
Çıxış verilənləri #2
9
4
4