Greater sum tree

Problem

Replace every key of a binary search tree by the sum of all keys that are greater than or equal to it. Print the new keys in inorder, separated by spaces.

Input, output and limits

Input: Line 1: the tree in level order, keys separated by spaces, with # for a missing child. The children of a missing node are not listed, and trailing # may be left out. A single # is an empty tree.
Output: The new keys in inorder order.
Constraints: 1 ≤ number of nodes ≤ 300
1 ≤ each key ≤ 1000000, all different

Examples

Example 1

Input

8 3 10 1 6 # 14 # # 4 7 13

Output

66 65 62 58 52 45 37 27 14

Example 2

Input

2 1 3

Output

6 5 3

Hints

Try the problem first. Open one hint at a time.

Hint 1

Visit the keys from largest to smallest: right subtree, node, left subtree.

Hint 2

Keep a running total and use it as the new value.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems