A terraced hillside is modeled as a binary tree of plots. Diagonals run down the slope: the root is on diagonal 0, following a right-child edge keeps you on the same diagonal, and following a left-child edge moves you to the next diagonal down (diagonal + 1). Thus a node's diagonal index equals the number of left-child edges on the path from the root to it. For each diagonal, report the sum of its node values, from diagonal 0 upward.

Input format

Line 1: an integer n, the number of tokens on the next line.

Line 2: n space-separated tokens describing a binary tree in level-order (breadth-first). The first token is the root's value. Reading left to right, keep a queue of already-created nodes; for each node taken from the front of the queue, the next two tokens are its left child then its right child, where the token null marks a missing child. Only non-null children are added to the queue. Trailing null tokens for absent children at the deepest level may be omitted. Every node value is an integer.

Output format

A single line: the value sum of each diagonal, from diagonal 0 to the deepest diagonal, space-separated.

Constraints

• 1 <= n <= 129
• The tree has at least 1 and at most 40 nodes.
• Each node value is an integer with -1000 <= value <= 1000.

7
3 9 20 null null 15 7

30 24

7
1 2 3 4 5 6 7

11 13 4