Ivan 喜欢汉堡和花钱。 Ivan 住的街上有 $$$n$$$ 汉堡店。 Ivan 有 $$$q$$$ 个朋友,第 $$$i$$$ 个朋友建议在 $$$l_i$$$ 会所见面,然后步行前往 $$$r_i$$$ $$$(l_i \leq r_i)$$$。当与第 $$$i$$$ 个朋友一起散步时,Ivan 可以访问满足 $$$l_i \leq x \leq r_i$$$ 的所有关节 $$$x$$$。
对于每个关节,Ivan 都知道其中最昂贵的汉堡的成本,它的成本为 $$$c_i$$$ burles。伊万想在途中参观一些餐馆,在每个餐馆中他都会买最贵的汉堡并花最多的钱。但有一个小问题:他的卡坏了,不再向他收取购物费用,而是卡上的金额发生了如下变化。
如果 Ivan 在购买之前有 $$$d$$$ burles,并且他在关节处花费了 $$$c$$$ burles,那么在购买之后他将拥有 $$$d \oplus c$$$ burles,其中 $$$\oplus$$$ 表示按位异或运算。
目前 Ivan 有 $$$2^{2^{100}} - 1$$$ burles,他想出去散步。帮助他确定如果他和朋友 $$$i$$$ 一起去散步,他可以花费的最大 burles 数量。他花费的 burles 金额定义为他帐户上的初始金额与最终帐户金额之间的差额。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500\,000$$$) — 汉堡店的数量。
下一行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq 10^6$$$),其中 $$$c_i$$$ — 汉堡店 $$$i$$$ 中最贵汉堡的成本。
第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 500\,000$$$) — Ivan 的朋友数量。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — Ivan 将行走的汉堡店数量对。
输出
输出 $$$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 只需要进入第一个汉堡即可。伊万和第二个朋友一起去了第三个汉堡。
在对第三个朋友(要从第一个汉堡走到第三个汉堡)的第二次测试中,只有 8 个花钱选项 - $$$0$$$、$$$12$$$、$$$14$$$、$$$23$$$、$$$12 \oplus 14 = 2$$$、$$$14 \oplus 23 = 25$$$、 $$$12 \oplus 23 = 27$$$,$$$12 \oplus 14 \oplus 23 = 20$$$。如果您去第一个和第三个汉堡,则结果花费的最大金额为 $$$12 \oplus 23 = 27$$$。