Delete a Two-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 two children. To make the deletion result unique, you must use the inorder successor of $x$, defined as the node with the smallest key in the right subtree of $x$.

Replace the key at the position of $x$ by the successor key, then delete the old successor node from its original position. The resulting tree must remain a BST.

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): $3\le n\le 20$.

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

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

Examples

Input

7
8 3 10 1 6 14 4
3

Output

8 4 1 6 10 14

Explanation

Node $3$ has two children. Its right subtree contains keys $6$ and $4$, whose minimum is $4$, so $4$ is the inorder successor.

Replace $3$ by $4$ and remove the old node $4$. The resulting preorder is 8 4 1 6 10 14.