题目描述

对于给定的由 $n$ 个整数组成的数组 $\{a_1,a_2,\dots,a_n\}$ ，每一次给出区间 $[l, r]$ ，你需要找到小于 $2^{31}$ 的最小非负整数 $x$ ，使得下式的答案最大：

$\displaystyle \sum_{i=l}^{r} \left( x \oplus a_i \right)$

其中，$\oplus$ 表示按位异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节 。

输入格式

第一行输入一个整数 $n \left( 1 \leq n \leq 10^5 \right)$ 代表数组中的元素数量。
第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( 1 \leq a_i \leq 10^9 \right)$ 代表数组中的元素。
第三行输入一个整数 $q \left( 1 \leq q \leq 10^5 \right)$ 代表询问次数。
此后 $q$ 行，每行输入两个整数 $l, r \left( 1 \leq l \leq r \leq n \right)$ 代表一次询问的区间。

输出格式

对于每一次询问，在单独的一行上输出一个最小的满足条件的正整数 $x \left( 0 \leq x < 2^{31} \right)$ 。

输入样例

5
4 78 12 1 3
3
2 5
1 4
3 3

输出样例

2147483632
2147483635
2147483635

说明/提示

对于第一组测试数据，题中的式子即 $x \oplus 78 + x \oplus 12 + x \oplus 1 + x \oplus 3 = 8\,589\,934\,494$ 。