来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 18 套，第 5 题。原题标号：E；原本地编号：Z4P1-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$ 时的答案。

样例输入1

2
6 2 4 7

样例输出1

19 17 11 7

样例解释1

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

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

样例输入2

3
1 2 3 4 5 6 7 8

样例输出2

36 35 33 30 26 21 15 8

样例输入3,4,5

见下发文件。

样例输出3,4,5

见下发文件。

数据范围与提示

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

测试点编号	$n\le$	特殊性质
$1,2$	$9$	否
$3$	$11$
$4$	$13$	是
$5$		否
$6$	$16$	是
$7$		否
$8$	$20$	是
$9,10$		否

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