Problem L: 有趣的运算符

Problem L: 有趣的运算符

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 170  Solved: 52
[Submit] [Status] [Web Board] [Creator:]

Description

有一个有趣的运算符⊕,它的名字叫 -- 异或。对,你没听错,就是位运算的那个异或,是不是听到位运算就感觉有点头疼?其实并不然。

有一天,无聊的学chang偶然间翻开某数论书,上面有一个关于函数f(x)的一个关系式:

是不是没怎么看懂这个关系式的意思?那学chang来给你们举个例子;

For example: f(1,2,4,8) = f(1⊕2,2⊕4,4⊕8) = f(3,6,12) = f(3⊕6,6⊕12) = f(5,10) = f(5⊕10) = f(15) = 15。

之后再给你一个区间l,r,让你求al,al+1,al+2...ar的最大值。嗯,就是这样。没看懂的可以看样例。

Input

测试数据有多组,对于每组测试数据:

第一行输入一个整数n (1 <= n <= 5000)

第二行输入n个整数 ai (0 <= ai <= 2^30 - 1)

第三行输入一个整数m,表示有m次查询(1 <= m <= 1000000)

接下来m行每行有一个l,r ( 1 <= l <= r <= n)

Output

对于每组测试数据的每次查询输出最大的ans值。

Sample Input Copy

3
8 4 1
2
2 3
1 2
6
1 2 4 8 16 32
4
2 5
3 4
1 2
1 6

Sample Output Copy

5
12
30
12
3
60

HINT

第一组样例:略。

第二组样例的最后一个m:取的是[3,6]这个区间使得答案最大为60