CF1100F.Ivan and Burgers

Ivan loves burgers and spending money. There are $n$ burger joints on the street where Ivan lives. Ivan has $q$ friends, and the $i$-th friend suggested to meet at the joint $l_i$ and walk to the joint $r_i$ $(l_i \leq r_i)$. While strolling with the $i$-th friend Ivan can visit all joints $x$ which satisfy $l_i \leq x \leq r_i$.

For each joint Ivan knows the cost of the most expensive burger in it, it costs $c_i$ burles. Ivan wants to visit some subset of joints on his way, in each of them he will buy the most expensive burger and spend the most money. But there is a small issue: his card broke and instead of charging him for purchases, the amount of money on it changes as follows.

If Ivan had $d$ burles before the purchase and he spent $c$ burles at the joint, then after the purchase he would have $d \oplus c$ burles, where $\oplus$ denotes the bitwise XOR operation.

Currently Ivan has $2^{2^{100}} - 1$ burles and he wants to go out for a walk. Help him to determine the maximal amount of burles he can spend if he goes for a walk with the friend $i$. The amount of burles he spends is defined as the difference between the initial amount on his account and the final account.

伊万喜欢汉堡和花钱。在伊万居住的街道上有 $n$ 家汉堡店。伊万有 $q$ 位朋友，其中第 $i$ 位朋友建议在第 $l_i$ 家店见面，然后一起步行到第 $r_i$ 家店（满足 $l_i \leq r_i$）。在与第 $i$ 位朋友散步途中，伊万可以访问所有满足 $l_i \leq x \leq r_i$ 的汉堡店 $x$。

对于每家汉堡店，伊万都知道其中最贵汉堡的价格，第 $i$ 家店的最贵汉堡价格为 $c_i$ 卢布。伊万希望在前往途中的某些店铺停留，并在每家停留的店铺购买最贵的汉堡，从而尽可能多地花钱。但这里有个小问题：他的银行卡坏了，无法正常扣款；取而代之的是，卡内余额会按如下方式变化：

若伊万在消费前有 $d$ 卢布，而在某家店花费了 $c$ 卢布，则消费后他的余额变为 $d \oplus c$ 卢布，其中 $\oplus$ 表示按位异或运算。

目前伊万卡内余额为 $2^{2^{100}} - 1$ 卢布，他准备出门散步。请帮助他计算：若他与第 $i$ 位朋友一同散步，他最多能“花费”多少卢布？此处“花费”的金额定义为账户初始余额与最终余额之差。

The first line contains one integer $n$ ($1 \leq n \leq 500\,000$) — the number of burger shops.

The next line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0 \leq c_i \leq 10^6$), where $c_i$ — the cost of the most expensive burger in the burger joint $i$.

The third line contains one integer $q$ ($1 \leq q \leq 500\,000$) — the number of Ivan's friends.

Each of the next $q$ lines contain two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$) — pairs of numbers of burger shops between which Ivan will walk.

第一行包含一个整数 $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$）——伊万的朋友数量。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——表示伊万将行走的汉堡店编号区间。

Output $q$ lines, $i$-th of which containing the maximum amount of money Ivan can spend with the friend $i$.

输出 $q$ 行，其中第 $i$ 行包含 Ivan 与第 $i$ 位朋友一起所能花费的最大金额。

In the first test, in order to spend the maximum amount of money with the first and third friends, Ivan just needs to go into the first burger. With a second friend, Ivan just go to the third burger.

In the second test for a third friend (who is going to walk from the first to the third burger), there are only 8 options to spend money — $0$, $12$, $14$, $23$, $12 \oplus 14 = 2$, $14 \oplus 23 = 25$, $12 \oplus 23 = 27$, $12 \oplus 14 \oplus 23 = 20$. The maximum amount of money it turns out to spend, if you go to the first and third burger — $12 \oplus 23 = 27$.

在第一个测试用例中，为了与第一位和第三位朋友花费最多的钱，伊万只需进入第一家汉堡店即可。对于第二位朋友，伊万只需前往第三家汉堡店。

在第二个测试用例中，对于第三位朋友（他将从第一家汉堡店走到第三家汉堡店），共有 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$。