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