1032-贪心 · 例11-毒瘤xor_2021秋季算法入门班第一章习题：模拟、枚举、贪心

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的由 $n$ 个整数组成的数组 $\{a_1,a_2,\dots,a_n\}$ ，每一次给出区间 $[l, r]$ ，你需要找到小于 $2^{31}$ 的最小非负整数 $x$ ，使得下式的答案最大：
$\displaystyle \sum_{i=l}^{r} \left( x \oplus a_i \right)$
$\hspace{15pt}$ 其中， $\oplus$ 表示按位异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节 。

输入描述:

第一行输入一个整数  代表数组中的元素数量。
第二行输入  个整数  代表数组中的元素。
第三行输入一个整数  代表询问次数。
此后  行，每行输入两个整数  代表一次询问的区间。

输出描述:

对于每一次询问，在单独的一行上输出一个最小的满足条件的正整数  。

示例1

输入

复制

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

输出

复制

2147483632
2147483635
2147483635

说明

对于第一组测试数据，题中的式子即  。