markdown

F. Ivan 与汉堡店

Ivan 喜欢汉堡和花钱。他住的街上共有 $n$ 家汉堡店。Ivan 有 $q$ 个朋友，第 $i$ 个朋友建议从第 $l_i$ 家店走到第 $r_i$ 家店（$l_i \le r_i$）。与第 $i$ 个朋友散步时，Ivan 可以访问所有满足 $l_i \le x \le r_i$ 的店铺 $x$。

对于每家店，Ivan 知道其中最贵汉堡的价格，第 $i$ 家店的价格为 $c_i$ 布勒斯。Ivan 想在散步途中访问一些店铺，并在每家访问的店铺中购买最贵的汉堡，尽可能多花钱。但有一个小问题：他的银行卡坏了，卡内余额的变化方式不是扣款，而是如下方式变化：

如果 Ivan 在购买前有 $x$ 布勒斯，并且在某家店花费了 $c$ 布勒斯，那么购买后他的余额变为 $x \oplus c$ 布勒斯，其中 $\oplus$ 表示按位异或运算。

目前 Ivan 的卡上有 $2^{100} - 1$ 布勒斯，他想要出去散步。请帮助他确定：如果他与第 $i$ 个朋友散步，最多能花费多少布勒斯。花费金额定义为初始余额与最终余额的差值。

输入

• 第一行包含一个整数 $n$（$1 \le n \le 500000$）—— 汉堡店的数量。
• 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^6$），其中 $c_i$ 是第 $i$ 家汉堡店中最贵汉堡的价格。
• 第三行包含一个整数 $q$（$1 \le q \le 500000$）—— Ivan 的朋友数量。
• 接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）—— Ivan 将与第 $i$ 个朋友散步的起点和终点店铺编号。

输出

输出 $q$ 行，第 $i$ 行包含 Ivan 与第 $i$ 个朋友散步时能花费的最大金额。

样例

样例输入 1

4
7 2 3 4
3
1 4
2 3
1 3

样例输出 1

7
3
7

样例输入 2

5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

样例输出 2

12
14
27
27
31
14
25
26
30
23
26
29
13
13
7

注释

在第一个样例中，为了与第一位和第三位朋友散步时花费最多钱，Ivan 只需要进入第一家汉堡店。与第二位朋友散步时，Ivan 只需要进入第三家汉堡店。

在第二个样例中，对于第三位朋友（从第 $1$ 家店走到第 $3$ 家店），共有 $8$ 种花钱方案：$0$、$12$、$14$、$23$、$12 \oplus 14 = 2$、$12 \oplus 23 = 25$、$14 \oplus 23 = 27$、$12 \oplus 14 \oplus 23 = 20$。如果去第一家店和第三家店，花费金额为 $12 \oplus 23 = 27$，这是最大可能的花费。