Знайдіть XOR на відрізку

Дуже проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

Задано масив $a$ . Потрібно обчислити значення операції XOR (побітове виключне "або") на заданому відрізку.

Вхідні дані

Перший рядок містить кількість елементів масиву $n (1 \leq n \leq 1 0^{6})$ .

Другий рядок містить $n$ цілих чисел $a_{i} (0 \leq a_{i} \leq 1 0^{9})$ — елементи масиву $a$ .

Третій рядок містить кількість запитів $q (1 \leq q \leq 1 0^{6})$ на пошук XOR на відрізку.

Кожен з наступних $q$ рядків містить по два цілих числа $l_{i}$ і $r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ — межі відрізка масиву, на якому потрібно знайти XOR.

Вихідні дані

Для кожного запиту в окремому рядку виведіть значення XOR елементів на відповідному відрізку масиву (включаючи межі).

Приклади

Вхідні дані #1

Відповідь #1

Відправки 317

Коефіцієнт прийняття 32%