题目内容

在一个文件系统中，目录被组织成 $n$ 层的完全二叉树结构，根目录位于第 0 层，最后一层是第 $n-1$ 层。每个目录自身可能包含一些文件，并且最多拥有两个子目录。现在需要对目录进行压缩处理：根据每个目录自身的文件大小，统计该目录连同其所有子目录一起的总大小。

已知输入按照完全二叉树的层序遍历顺序，给出每个目录自身的文件大小，并将其中第 $i$ 个元素记为 $m[i]$。若某个位置没有目录，用 -1 表示；若某个目录自身没有文件，但可能还有子目录，用 0 表示。

对一个存在的目录，它的总大小等于自身文件大小加上左、右子目录总大小。若某个子目录不存在或为空，则其总大小按 0 处理。由于一个目录的总大小依赖其子目录的统计结果，因此需要从最后一层开始，自底向上逐层计算。

约束条件：目录层数 $n$ 满足 1 <= n <= 10；输入中每个目录自身文件大小 $m[i]$ 满足 -1 <= m[i] <= 10。

输入描述

输入共两行。

第一行包含一个整数 $n$，表示目录树的层数。

第二行包含若干个由空格分隔的整数，表示按完全二叉树层序遍历给出的第 0 层到第 $n-1$ 层各目录自身的文件大小。第 $n-1$ 层末尾连续的空节点可以省略。

输出描述

输出一行，包含若干个由单个空格分隔的整数，表示按相同层序遍历顺序排列的每个目录统计后的总大小。空节点输出 -1。末尾连续的空节点不输出，且行末不能有多余空格。

样例1

输入

1
5

输出

5

说明

层数 n=1，目录树只有根目录一个节点。

根目录自身文件大小为 5，它没有任何子目录。

因此根目录的总大小就是自身文件大小 5。

末尾没有需要省略的空节点，直接输出 5。

样例2

输入

2
1 2 3

输出

6 2 3

说明

目录树共有 2 层，即根目录和两个子目录。

两个子目录的自身文件大小分别为 2 和 3，它们都没有下一层子目录，所以总大小分别是 2 和 3。

根目录自身文件大小为 1，加上左子总大小 2 和右子总大小 3，得到 $1+2+3=6$。

因此按层序输出为 6 2 3。

样例3

输入

3
2 -1 3 -1 -1 4

输出

9 -1 7 -1 -1 4

说明

输入的树结构如图：

样例4

输入

3
0 1 2 3 0 -1 -1

输出

6 4 2 3 0

说明

输入的树结构如图：