题目描述

$sgly$有$N$个数$a_1, a_2, ..., a_N$，给出$q$个询问，每次询问给出区间$[L, R]$，现在请你找到一个数$X$，

使得$0 \leq X < 2^{31}$ $\sum_{i=L}^{R} X \oplus a_i$ 最大，$\oplus$ 表示异或操作

输入格式

第一行一个整数$N$，表示序列的长度

第二行$N$个整数，表示序列内的元素

第三行一个整数$q$，表示询问的个数

接下来$q$行，每行两个整数$[L, R]$，表示询问的区间

输出格式

输出$q$行，每行一个整数表示答案

若有多组可行解，请输出较小的解

样例

输入

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

输出

2147483632
2147483635
2147483635

数据范围与提示

$1 \leq n, q ≤ 10^5$

$1 \leq L \leq R \leq n$

$a_i < 2^{31}$