Delete a Leaf from a BST

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from $a_1,a_2,\ldots,a_n$ in the given insertion order. Duplicate keys are ignored.

A key $x$ is guaranteed to exist, and its node is guaranteed to be a leaf, meaning that it has neither a left child nor a right child.

Delete the node with key $x$, then print the preorder traversal of the remaining tree. Preorder visits the root, then the left subtree, then the right subtree.

If $x$ is the only node, the tree becomes empty after deletion.

Input

The first line contains $n$.

The second line contains $n$ signed integers $a_1,a_2,\ldots,a_n$.

The third line contains the key $x$ to delete.

Output

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

If it is empty, print EMPTY.

Subtasks

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

Subtask 2 (30 points): $1\le n\le 5000$.

Subtask 3 (50 points): $1\le n\le 200000$.

In all subtasks, $a_i$ and $x$ are signed 64-bit integers, duplicate insertion keys are ignored, and the node with key $x$ exists and has exactly $0$ children.

Examples

Input

7
8 3 10 1 6 14 4
4

Output

8 3 1 6 10 14

Explanation

In the constructed BST, node $4$ is the left child of node $6$ and has no children, so it is a leaf. Removing it leaves all other links unchanged.

The resulting preorder traversal is 8 3 1 6 10 14.