题目描述

有一个长度为$2^N$的整数序列$A_0, A_1, ..., A_{2^N-1}$。注意，序列是以$0$为起始索引的。

对于满足$1 \leq K \leq 2^N-1$的每个整数$K$，解决以下问题：

• 令$i$和$j$为整数。找到满足$0 \leq i < j \leq 2^N-1$和$(i$ $or$ $j) \leq K$的$A_i + A_j$的最大值，这里的$or$表示按位或运算。

约束条件

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_0$ $A_1$ $...$ $A_{2^N-1}$

输出

打印出$2^N-1$行。第$i$行打印出上述问题中$K=i$时的答案。

示例输入 1

2
1 2 3 1

示例输出 1

3
4
5

对于$K=1$，唯一可能的$i$和$j$的组合是$(i,j)=(0,1)$，所以答案是$A_0+A_1=1+2=3$。

对于$K=2$，可能的$i$和$j$的组合是$(i,j)=(0,1),(0,2)$。当$(i,j)=(0,2)$时，$A_i+A_j=1+3=4$。这是最大值，所以答案是$4$。

对于$K=3$，可能的$i$和$j$的组合是$(i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)$。当$(i,j)=(1,2)$时，$A_i+A_j=2+3=5$。这是最大值，所以答案是$5$。

示例输入 2

3
10 71 84 33 6 47 23 25

示例输出 2

81
94
155
155
155
155
155

示例输入 3

4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

示例输出 3

101
120
147
156
156
178
194
194
194
194
194
194
194
194
194