У Назара есть любимое число 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 строк, ответы на запросы.