普及模拟赛 18 - E

有 $2^n$ 个小朋友排成一排，从左往右下标从 $0$ 到 $2^{n}-1$ ，第 $i$ 个小朋友的力气值为 $a_i$ ，老师要选出一些小朋友参加拔河比赛。

小朋友会跟着老师的口号变换队形，老师会喊恰好一次口号，当老师喊出口号 $x$ 时，原本第 $i$ 个小朋友会走到原本第 $i \oplus x$ 个小朋友的位置上去，其中必须满足 $0 \leq x < 2^{n}$ 。

变换完队形后，老师会把所有小朋友重新按照从左往右的顺序编号，其中第一个小朋友编号为 $0$ ，第二个小朋友编号为 $1$ ，以此类推，重新编号后，老师会让编号大于等于 $k$ 的小朋友全部出列参加拔河比赛，此时队伍的力气值为所有出列的小朋友的力气值之和。

然而，目前并不知道参加拔河比赛的具体人数，因此，你需要对 $0 \leq k < 2^n$ ，依次输出在选择合适的口号的情况下，所有出列的小朋友的力气值之和最大可以是多少。

第一行一个非负整数 $n$ 。

第二行 $2^n$ 个非负整数，描述数组 $a$ 。

共一行 $2^n$ 个整数，表示 $k=0,1,\dots,2^n-1$ 时的答案。

2
6 2 4 7

19 17 11 7

对于 $k=1$ ，选择口号 $x=1$ 。

对于 $k=0,2,4$ ，选择口号 $x=0$ 。

3
1 2 3 4 5 6 7 8

36 35 33 30 26 21 15 8

见下发文件。

见下发文件。

$0\le n\le 20,0\le a_i\le 10^9$ 。

特殊性质：至多只有 $n$ 个 $i$ 满足 $a_i>0$ 。