Remove an order number

Problem

Delete a key from a binary search tree. A node with two children is replaced by its inorder successor, the smallest key of its right subtree. If the key is not in the tree, nothing changes. Print the preorder keys of the final tree, or empty if no key is left.

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 delete.
Output: Preorder keys separated by spaces, or the word empty.
Constraints: 0 ≤ number of nodes ≤ 300
1 ≤ each key ≤ 1000000, all different

Examples

Example 1

Input

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

Output

8 4 1 6 7 10 14 13

Example 2

Input

5
5

Output

empty

Hints

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

Hint 1

A leaf is removed. A node with one child is replaced by that child.

Hint 2

With two children, copy the smallest key of the right subtree into the node, then delete that key from the right subtree.

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