CF1771F.Hossam and Range Minimum Query

Hossam gives you a sequence of integers $a_1, \, a_2, \, \dots, \, a_n$ of length $n$. Moreover, he will give you $q$ queries of type $(l, \, r)$. For each query, consider the elements $a_l, \, a_{l + 1}, \, \dots, \, a_r$. Hossam wants to know the smallest number in this sequence, such that it occurs in this sequence an odd number of times.

You need to compute the answer for each query before process the next query.

霍萨姆给你一个长度为 $n$ 的整数序列 $a_1, \, a_2, \, \dots, \, a_n$。此外，他还会给出 $q$ 个形如 $(l, \, r)$ 的查询。对于每个查询，考虑子序列 $a_l, \, a_{l + 1}, \, \dots, \, a_r$。霍萨姆想知道该子序列中出现次数为奇数次的最小数字。

你需要在处理下一个查询之前，先为当前查询计算出答案。

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$), the length of the sequence.

The second line contains $n$ integers $a_1, \, a_2, \, \dots, \, a_n$ ($1 \le a_i \le 10^9$).

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$), the number of queries.

Each of the next $q$ lines contains two integers $a$ and $b$ ($0 \le a, \, b \le 2 \cdot 10^9$), the numbers used to encode the queries.

Let $\mathrm{ans}_i$ be the answer on the $i$-th query, and $\mathrm{ans}_0$ be zero. Then $$l_i = a_i \oplus \mathrm{ans}_{i - 1},$$ $$r_i = b_i \oplus \mathrm{ans}_{i - 1},$$ where $l_i, \, r_i$ are parameters of the $i$-th query and $\oplus$ means the bitwise exclusive or operation. It is guaranteed that $1 \le l \le r \le n$.

输入的第一行包含一个整数 $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 = 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$。

For each query, print the smallest number that occurs an odd number of times on the given segment of the sequence.

If there is no such number, print $0$.

对于每个查询，输出给定序列区间内出现奇数次的最小数字。

如果不存在这样的数字，则输出 $0$。

In the example,

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.

在示例中，

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.