На астероиде в сторону Земли летят $$$n$$$ симбиотов. Чтобы пережить долгий перелет, симбиоты расположились в самой благоприятной для космических полётов формации — по кругу. Известно, что $$$i$$$-й из симбиотов в порядке по часовой стрелке имеет массу $$$a_i$$$. Не чаще, чем раз в год, один из еще живых симбиотов жертвует собой ради выживания других. Если $$$i$$$-й симбиот жертвует собой, его соседи, находящиеся на местах $$$(i + 1) \bmod n$$$ и $$$(i - 1) \bmod n$$$, ассимилируют по его половине (округленной вниз до целого, если его масса была нечетна), прибавляя ассимилированную массу к своей. На месте пожертвовавшего собой симбиота остается пустое место, которое никто не занимает. Если с какой-то стороны от жертвующего собой симбиота уже находится пустое место, его соответствующая половина никем не ассимилируется и просто исчезает в космосе.
В некоторые года симбиоты спокойно продолжают свой перелет и никто собой не жертвует.
Карлтон Дрейк из «Фонда жизни» собирался отправить к этому астероиду ракету, но ему не было известно, сколько точно лет она будет лететь до астероида. Поэтому он рассчитал $$$q$$$ возможных наиболее вероятных времен полета $$$t_i$$$ и захотел для каждого из них узнать, симбиот с каким наибольшим весом может его ждать на астероиде.
Разумеется, он в свое время смог посчитать интересующие его величины. А можете ли их восстановить вы?
В первой строке ввода дано целое число $$$n$$$ — изначальное количество симбиотов на астероиде ($$$3 \leqslant n \leqslant 2 \cdot 10^4$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — изначальные массы симбиотов ($$$1 \leqslant a_i \leqslant 10^9$$$).
В третьей строке ввода дано целое число $$$q$$$ — количество запросов, ответы на которых интересовали Дрейка ($$$1 \leqslant m \leqslant 2 \cdot 10^5$$$).
В следующей строке через пробел перечислены сами запросы $$$t_i$$$ — ожидаемые времена полета, для которых требуется найти максимальную возможную массу симбиота на астероиде спустя ровно столько времени ($$$1 \leqslant t_i \leqslant n$$$).
Выведите $$$q$$$ строк, по строке на каждый запрос. В $$$i$$$-й строке выведите максимальную достижимую за $$$t_i$$$ лет каким-либо симбиотом массу.
3 1 4 7 2 1 2
9 10
5 1 3 5 7 9 3 1 2 5
12 13 15
4 2 4 8 16 4 1 2 3 4
20 21 23 23