Add a new order number

Problem

Insert a key into a binary search tree. If the key is already in the tree, change nothing. Print the keys of the final tree in preorder (node, left subtree, right subtree), 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. Line 2: the key to insert.
Output: The preorder keys of the tree after the insert.
Constraints: 0 ≤ number of nodes ≤ 300
1 ≤ each key ≤ 1000000

Examples

Example 1

Input

8 3 10
6

Output

8 3 6 10

Example 2

Input

8 3 10
10

Output

8 3 10

10 is already there.

Hints

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

Hint 1

Follow the search path until a child is missing, then attach the new node there.

Hint 2

Do nothing when the key equals a node's key.

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