Delete a One-Child Node 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 insertion order. Duplicate keys are ignored.

A key $x$ is guaranteed to exist, and its node has exactly one child. When deleting $x$, that unique child takes the position of $x$:

• if $x$ is not the root, the parent of $x$ is connected directly to the unique child;
• if $x$ is the root, the unique child becomes the new root.

Print the preorder traversal after the 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

Print the preorder traversal of the resulting tree on one line, with keys separated by one space.

Subtasks

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

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

Subtask 3 (50 points): $2\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 $1$ child.

Examples

Input

4
8 3 10 14
10

Output

8 3 14

Explanation

Node $10$ is the right child of $8$ and has exactly one child, $14$. After deleting $10$, node $14$ is connected directly as the right child of $8$.

The resulting preorder traversal is 8 3 14.