H. 落叶

题目描述

给一棵二叉树，每个节点都有一个水平位置：左儿子在它左边 $1$ 个单位，右儿子在它右边 $1$ 个单位。从左向右输出每个水平位置的所有结点的权值之和。按照先序遍历的方式输入，左或右儿子为空时，用 $-1$ 表示。

输入格式

输入若干个数，表示一棵树。

输出格式

输出一行，若干个数，从左向右输出每个水平位置的所有结点的权值之和。

样例

输入样例 1

5 7 -1 6 -1 -1 3 -1 -1

输出样例 1

7 11 3

输入样例 2

8 2 9 -1 -1 6 5 -1 -1 12 -1 -1 3 7 -1 -1 -1

输出样例 2

9 7 21 15

数据范围与提示

• $50\%$ 的数据：$n \le 1000$
• $100\%$ 的数据：$n \le 100000$，节点的权值为正数