Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$ и целое число $K$. Напишите программу, которая обрабатывает следующие запросы:

• l r: выведите количество пар $(i, j)$ таких, что $l \le i \le j \le r$ и XOR элементов $A_i, A_{i+1}, \ldots, A_j$ равен $K$.

Входные данные

Первая строка содержит два целых числа $N$ $(1 \le N \le 100{,}000)$ и $K$ $(0 \le K \le 1{,}000{,}000)$.

Вторая строка содержит $N$ целых чисел $A_1, A_2, \ldots, A_N$. $(0 \le A_i \le 1{,}000{,}000)$

Третья строка содержит целое число $M$ $(1 \le M \le 100{,}000)$ — количество запросов.

Следующие $M$ строк содержат по два целых числа $l, r$, представляющих запрос. $(1 \le l \le r \le N)$

Выходные данные

Для каждого запроса выведите строку с одним целым числом — ответом.

Примеры

Входные данные 1

6 3
1 2 1 1 0 3
2
1 6
3 5

Выходные данные 1

7
0

Входные данные 2

5 1
1 1 1 1 1
3
1 5
2 4
1 3

Выходные данные 2

9
4
4