F. Хоссам и минимум на отрезке
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хоссам дал вам последовательность целых чисел $$$a_1, \, a_2, \, \dots, \, a_n$$$ длины $$$n$$$. Кроме того, он последовательно дает вам $$$q$$$ запросов вида $$$(l, \, r)$$$. Для каждого запроса он хочет знать среди чисел $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$ такое минимальное число, что оно встречается в заданном отрезке последовательности нечетное количество раз.

Вы должны посчитать ответ на каждый запрос, прежде чем отвечать на следующий.

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

В первой строке входных данных задано единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина последовательности.

Во второй строке входных данных задана последовательность из $$$n$$$ целых чисел $$$a_1, \, a_2, \, \dots, \, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

В третьей строке задано целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк, в каждой из которой задано два целых числа $$$a$$$ и $$$b$$$ ($$$0 \le a, \, b \le 2 \cdot 10^9$$$) — числа, с помощью которых кодируются границы запроса.

Пусть $$$\mathrm{ans}_i$$$ ответ на $$$i$$$-й запрос, и $$$\mathrm{ans}_0$$$ равен нулю. Тогда $$$$$$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$$$$$ $$$$$$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$$$$$ где $$$l_i, \, r_i$$$ параметры $$$i$$$-го запроса и $$$\oplus$$$ означает битовое исключающие или. Гарантируется, что $$$1 \le l \le r \le n$$$.

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

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

Если такого числа не существует, выведите $$$0$$$.

Примеры
Входные данные
5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7
Выходные данные
1
2
1
0
2
2
Входные данные
10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61
Выходные данные
51
55
19
48
76
19
23
19
55
19
Примечание

В данном примере

$$$$$$l_1 = 1, \, r_1 = 2,$$$$$$ $$$$$$l_2 = 1, \, r_2 = 3,$$$$$$ $$$$$$l_3 = 2, \, r_3 = 4,$$$$$$ $$$$$$l_4 = 1, \, r_4 = 4,$$$$$$ $$$$$$l_5 = 2, \, r_5 = 2,$$$$$$ $$$$$$l_6 = 1, \, r_6 = 5.$$$$$$