Моана отправилась в путешествие на своем каноэ, чтобы спасти свой остров. Для этого ей нужно собрать специальные магические ракушки, расположенные на $$$2^n$$$ островах. Количество магических ракушек на $$$i$$$-м острове равно $$$a_i$$$, причем острова нумеруются с нуля и до $$$2^n - 1$$$.
Моана хочет собрать как можно больше ракушек как можно быстрее, поэтому хочет посетить два острова и собрать все ракушки на них. Но может случиться такое, что богиня огня Те Ка будет препятствовать ей в ее приключении, и Моана сможет посетить два острова с номерами $$$i$$$ и $$$j$$$ только если $$$i\ |\ j \leq k$$$, где $$$|$$$ означает операцию побитового «или».
Величина $$$k$$$ заранее неизвестна, поэтому помогите Моане для каждого $$$k$$$ от $$$1$$$ до $$$2^n - 1$$$ найти $$$\max\limits_{i\,|\,j \le k} a_i + a_j$$$. Еще раз обратим внимание, что номера островов начинаются с нуля, иными словами, их двоичные записи идут от $$$n$$$ нулей до $$$n$$$ единиц.
В первой строке дано целое число $$$n$$$, означающее, что всего есть $$$2^n$$$ островов с ракушками $$$1 \leq n \leq 18$$$.
Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — количество ракушек на каждом острове ($$$1 \le a_i \le 10^9$$$).
Для каждого $$$k$$$ от $$$1$$$ до $$$2^n - 1$$$ выведите ответ на задачу — максимальную достижимую с таким $$$k$$$ величину $$$a_i + a_j$$$. Ответы для разных $$$k$$$ разделяйте пробелами.
1 10 20
30
2 1 2 3 1
3 4 5
3 1 2 3 4 5 6 7 8
3 4 7 7 11 12 15