Ваня очень любит бургеры, а так же очень любит тратить деньги. На улице, где живет Ваня, находится $$$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$$$.
| Codeforces Round 532 (Div. 2) |
|---|
| Закончено |
