Preorder listing

Problem

Print the values of the tree in preorder order, separated by single spaces. Preorder handles a node first, then its left side, then its right side.

Input: Line 1: the tree in level order, values separated by spaces, with null for a missing child. The tree has at least one node.
Output: The values on one line, separated by spaces.
Constraints: 1 ≤ number of nodes ≤ 3000
-1000 ≤ each value ≤ 1000

Example 1

Input

1 2 3 4 5 null 6

Output

1 2 4 5 3 6

Prints 1 2 4 5 3 6.

Example 2

Input

Output

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

Hint 1

Write the node's value before the two recursive calls.

Hint 2

Use one list that all calls add to.

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