Delete Node in a BST

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST by inserting the $n$ distinct keys $a_1,a_2,\ldots,a_n$ in the given order. Then delete key.

If key is absent, leave the tree unchanged. If the node exists:

• remove it directly if it has no child;
• replace it by its only child if it has exactly one child;
• if it has two children, replace it by its inorder successor, the node with the smallest key in its right subtree, then remove that successor from its old position.

The successor rule in the two-child case makes the resulting tree unique in this version.

Print the preorder traversal after the operation.

Input

The first line contains $n$.

If $n>0$, the next line contains the $n$ distinct keys $a_1,a_2,\ldots,a_n$. If $n=0$, this line is absent.

The last line contains key.

Output

If the resulting tree is non-empty, print its preorder keys separated by one space.

If the tree is empty, print EMPTY.

Subtasks

Subtask 1 (20 points): $0\le n\le 20$.

Subtask 2 (30 points): $0\le n\le 500$.

Subtask 3 (50 points): $0\le n\le 10^4$.

In all subtasks, the tree keys are distinct and $-10^5\le a_i,\text{key}\le 10^5$.

Examples

Input

7
5 3 6 2 4 7 1
3

Output

5 4 2 1 6 7

Explanation

Node $3$ has two children. The minimum key in its right subtree is $4$, so $4$ is its inorder successor.

Replace $3$ by $4$ and remove the old node $4$. The resulting preorder is 5 4 2 1 6 7.