F. Ваня и бургеры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваня очень любит бургеры, а так же очень любит тратить деньги. На улице, где живет Ваня, находится $$$n$$$ бургерных.

У Вани есть $$$q$$$ друзей, $$$i$$$-й друг предложил Ване встретиться у бургерной с номером $$$l_i$$$ и прогуляться до бургерной $$$r_i$$$ $$$(l_i \leq r_i)$$$. Во время прогулки с $$$i$$$-м другом Ваня может зайти во все бургерные с номерами $$$x$$$ такими, что $$$l_i \leq x \leq r_i$$$.

Для каждой бургерной Ваня знает стоимость самого дорогого бургера $$$c_i$$$ бурлей. Ваня хочет зайти в какое-то подмножество бургерных по пути, взять в каждой из них самый дорогой бургер и потратить как можно больше денег. Но есть небольшая проблема: карта Вани сломалась, и вместо того, чтобы снимать деньги после покупки, количество денег на карте меняется следующим образом.

Пусть до покупки у Вани было $$$d$$$ бурлей и Ваня потратил $$$c$$$ бурлей в бургерной, тогда после этих действий у Вани на счете останется $$$d \oplus c$$$ бурлей, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Сейчас на счету Вани $$$2^{2^{100}} - 1$$$ бурлей и он уже собирается на прогулку. Помогите Ване узнать, какое максимальное количество денег он сможет потратить, если пойдет гулять с другом под номером $$$i$$$. Количество бурлей, потраченных Ваней, определяется как разность между начальным количеством бурлей на счете Вани и конечным количеством бурлей на его счете.

Входные данные

В первой строке находится одно целое число $$$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$$$) — пара номеров бургерных, между которыми совершается прогулка.

Выходные данные

Выведите $$$q$$$ строк, в $$$i$$$-й строке выведите максимальное количество денег, которое Ваня может потратить вместе с другом под номером $$$i$$$.

Примеры
Входные данные
4
7 2 3 4
3
1 4
2 3
1 3
Выходные данные
7
3
7
Входные данные
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
Выходные данные
12
14
27
27
31
14
25
26
30
23
26
29
13
13
7
Примечание

В первом тесте для того, чтобы потратить максимальное количество денег с первым и третьим другом, Ване достаточно зайти в первую бургерную. Со вторым другом Ване достаточно зайти в третью бургерную. Во втором тесте для третьего друга (который собирается прогуляться от первой до третьей бургерной) всего есть 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$$$.