简单的异或
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

    小Y学过异或后觉得这太简单了，但小H认为小Y太天真了，决定考验一下他，出了一道题：
    给出一个数组a，长度为n，分别为a_1,a_2,a_3,...a_{n-1},a_n。以及q次访问，每次给出两个整数 l，r表示区间的左右端点。
    对于每次访问，给出一个整数 x(x < 2^{31}) 使得\sum_{i=l }^{r}(x⊕a_i )最大 

输入描述:

第一行一个整数N (1\le N \le 10^5 )，表示序列的长度
第二行N个整数，表示序列内的元素(1\le a_i<2^{31} )
第三行一个整数q，表示询问的个数(1\le q \le 10^5 )
接下来q行，每行两个整数 L,R，表示询问的区间
保证L\le R

输出描述:

对于每次访问输出一个对应的x，若有多个解则输出最小的解
示例1

输入

复制 
5
1 2 3 4 5
3
1 2
2 4
3 5

输出

复制 
2147483644
2147483645
2147483642

说明

第一个样例中，
第一次访问区间[1,2]
区间内的值为1,2
当x取2147483644即1111111111111111111111111111100（31位二进制）时
x^1+x^2的值最大