Маленькая Мишка увлекается программированием. Поскольку совсем недавно прошёл её День Рождения, то друзьями было принято решение подарить ей массив целых неотрицательных чисел a1, a2, ..., an из n элементов!
Мишке массив очень понравился, и она сразу же захотела определить его красоту, но она ещё маленькая и плохо работает с большими массивами. Именно поэтому она пригласила Вас к себе в гости и попросила ответить на m запросов.
Каждый запрос определяется следующим образом:
- Выбираются числа l и r (1 ≤ l ≤ r ≤ n) — границы отрезка запроса.
- Из отрезка массива [l, r] (из набора чисел al, al + 1, ..., ar) по одному разу выписываются все числа, входящие в заданный отрезок чётное число раз.
- Считается XOR-сумма всех выписанных чисел, которая и является ответом на запрос. Формально, если в пункте 2 выписаны числа x1, x2, ..., xk, то Мишку интересует значение
, где 
— операция побитового исключающего ИЛИ.
Поскольку одни только маленькие медвежата знают определение красоты массива, то всё, что от вас требуется, — ответить на каждый из предложенных запросов.
Выходные данные
Выведите m целых неотрицательных чисел — ответы на запросы в порядке их появления во входных данных.
Примечание
Рассмотрим второй пример:
В отрезок из первого запроса ни одно число не входит чётное число раз — ответ 0.
Во втором запросе такое число единственное и равно 3 — ответ 3.
В третьем запросе выписывается только число 1 — ответ 1.
В четвёртом запросе рассматриваются все элементы массива массив. Только числа 1 и 2 входят в него чётное число раз. Ответ равен 3.
В пятом запросе запросе выписываются числа 1 и 3. Ответ — 
.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 7 8
1
1 3
|
0
|
|
2
|
7
1 2 1 3 3 2 3
5
4 7
4 5
1 3
1 7
1 5
|
0
3
1
3
2
|