题目描述

長さ $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$ はビットごとの論理和を表す。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$2^N-1$ 行出力せよ。 $i$ 行目には、$K=i$ のときの上記の問題の答えを出力せよ。

题目大意

给你一个长度为 $2^n$ 的序列 $a$，每个$1\le K\le 2^n-1$，找出最大的 $a_i+a_j$（$i \mathbin{\mathrm{or}} j \le K$，$0 \le i < j < 2^n$）并输出。
$\mathbin{\mathrm{or}}$ 表示按位或运算。

2
1 2 3 1

3
4
5

3
10 71 84 33 6 47 23 25

81
94
155
155
155
155
155

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

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

提示

制約

• $1\ \leq\ N\ \leq\ 18$
• $1\ \leq\ A_i\ \leq\ 10^9$
• 入力はすべて整数である。

Sample Explanation 1

$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$ です。