Inorder listing

Problem

Print the values of the tree in inorder order, separated by single spaces. Inorder handles the left side first, then the node, then the 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

4 2 5 1 3 6

Prints 4 2 5 1 3 6.

Example 2

Input

Output

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

Hint 1

Write the node's value between 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.