Hossam 为您提供长度为 $$$n$$$ 的整数序列 $$$a_1, \, a_2, \, \dots, \, a_n$$$。此外,他会给你 $$$q$$$ 类型的 $$$(l, \, r)$$$ 查询。对于每个查询,考虑元素 $$$a_l, \, a_{l + 1}, \, \dots, \, a_r$$$。 Hossam 想要知道该序列中最小的数字,以便它在此序列中出现奇数次。
在处理下一个查询之前,您需要计算每个查询的答案。
输入
输入的第一行包含一个整数 $$$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$$$。
示例
输入 #1
5 1 2 1 2 2 6 1 2 0 2 0 6 0 5 2 2 3 7
输出 #1
1 2 1 0 2 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
输出 #2
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。$$$$$$