Rosemoe 有 朵萌萌的玫瑰，她们排成了一列。每朵玫瑰都有一个美丽贡献度。第 朵玫瑰拥有 的美丽贡献度。由于 Rosemoe 照顾不周，可能有些玫瑰枯萎了，她的美丽贡献度不是正数，而是零或负数。

Rosemoe 将几朵玫瑰的美丽值定义为这几朵玫瑰的美丽贡献度相或。形式化地来说，如果有 朵玫瑰，其中第 朵的美丽贡献度为 ， 那么这几朵玫瑰的美丽值为 （其中 表示按位或）。注意：本题中进行或运算时，均以C/C++中的64位有符号整数（long long）的或运算实现。负数的符号位总是 。特别地，我们认为 朵玫瑰的美丽值为 。

Rosemoe 突然有一个问题：如果她从这一列玫瑰中一个区间 中选取一些玫瑰（ 朵或更多），选出的这些玫瑰的美丽值的最大值是多少？

现在 Rosemoe 有 个询问，第 个询问的区间为 ，对于每个询问，你需要求出上述问题的答案。各个询问是相互独立的。

第一行一个整数  ，表示玫瑰的数量。

第二行  个整数，第  个整数表示第  朵玫瑰的美丽贡献度  。

第三行一个整数 ，表示询问的数量。

接下来  行，第  行有两个整数，分别为  。数据保证  ， 且  。

输出  行，每行一个整数。第  行的整数表示第  个询问的答案。

10
1 1 -4 5 14 19 -19 8 1 0
5
1 10
1 4
2 8
3 3
6 10

31
5
31
0
27

对于第二个询问，我们可以选择第  朵玫瑰，答案为  .

对于第四个询问，我们不从区间中选取玫瑰，答案为  .

对于第五个询问，我们可以选择第  朵玫瑰，答案为  .