题目描述

莫阿娜乘着她的独木舟出发去拯救她的岛屿。为此，她需要收集分布在 $2^n$ 个岛屿上的特殊魔法贝壳。第 $i$ 个岛屿上的魔法贝壳数量为 $a_i$，岛屿编号从 $0$ 到 $2^n - 1$。

莫阿娜希望尽可能快地从尽可能多的岛屿上收集贝壳，因此她想要访问两个岛屿并收集这两个岛屿上的所有贝壳。但火神 Te Ka 可能会阻碍她的冒险，只有当 $i\ |\ j \leq k$ 时，莫阿娜才能访问编号为 $i$ 和 $j$ 的两个岛屿，其中 $|$ 表示按位 或 运算。

$k$ 的值是预先未知的，因此请帮助莫阿娜为每个 $k$ 从 $1$ 到 $2^n - 1$ 找到 $\max\limits_{i\,|\,j \le k} a_i + a_j$。再次注意，岛屿编号从 $0$ 开始，换句话说，它们的二进制表示范围是从 $n$ 个 $0$ 到 $n$ 个 $1$。

输入格式

第一行包含一个整数 $n$，表示总共有 $2^n$ 个拥有贝壳的岛屿（$1 \leq n \leq 18$）。

第二行列出 $2^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