Azber는 Biou의 집에서 게임을 한다

Azber는 Biou의 집에 놀러 가서 게임을 한다. Biou의 집에는 지하 $0$층부터 $N-1$층까지 있으며, $i$층에는 $2^i$번부터 $2^{i+1}-1$번까지의 방이 있다. 각 방에는 수가 부여되는데, $j$ ($1 \leq j \leq 2^N-1$)번 방에는 수 $a_j$가 부여된다.

방 사이에는 통로가 있다. 같은 층에서 번호가 인접한 방끼리는 양방향 통로로 이어진다. $i>1$인 모든 방 $i$에서는 $\lfloor \frac{i}{2} \rfloor$번 방으로 가는 단방향 통로가 있다.

Azber와 Biou는 Azber부터 번갈아 가며 로봇을 조종한다. 게임을 시작하기 전에 로봇을 놓을 방은 두 사람이 합의하여 정한다. 각 플레이어는 자신의 차례에 다음 중 하나를 선택할 수 있다.

• 로봇을 통로를 따라 다른 방으로 이동시킨다. 로봇은 이전에 방문했던 방으로 다시 이동할 수 없다. 처음에 로봇이 있던 방도 방문한 방으로 본다.
• 게임의 종료를 선언한다.

플레이어가 게임의 종료를 선언하면 게임이 끝난다. 로봇이 1번 방에 있으면 더 이상 움직일 곳이 없으므로 게임이 끝난다. 점수는 로봇이 방문한 방에 부여된 수의 합이다. Azber는 점수를 최대한 작게 하고 싶고, Biou는 최대한 크게 하고 싶다. 두 사람은 항상 최적으로 플레이한다.

Azber와 Biou는 모든 방에 대해, 로봇을 그 방에서 시작했을 때의 최종 점수가 궁금하다. 각 방에서 시작할 때의 최종 점수를 구하시오.

첫 번째 줄에 Biou의 집의 층 수 $N$이 주어진다. ($1 \leq N \leq 11$)

두 번째 줄에 1번 방부터 $2^N-1$번 방까지 각 방에 부여된 수 $a_1, a_2, \cdots, a_{2^N-1}$이 공백으로 구분되어 주어진다. ($-10^9 \leq a_i \leq 10^9$, $a_i$는 정수)

$2^N-1$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 로봇을 $i$번 방에서 시작했을 때의 최종 점수이다.