Долгое путешествие

На астероиде в сторону Земли летят $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$ лет каким-либо симбиотом массу.