Insert a Key Sequence into a BST

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Initially the binary search tree (BST) is empty. Process $a_1,a_2,\ldots,a_n$ in order:

• If the tree is empty, the inserted key becomes the root.
• At a node with key $v$, continue to the left child if $a_i<v$ and to the right child if $a_i>v$.
• If the required child is empty, create a new node with key $a_i$ there.
• If $a_i=v$ at an existing node, ignore this insertion; the BST stores no additional copy of a duplicate key.

After all insertions, describe the resulting tree using two traversals:

• preorder: root, left subtree, right subtree;
• inorder: left subtree, root, right subtree.

Input

The first line contains $n$.

If $n>0$, the next line contains $n$ signed integers $a_1,a_2,\ldots,a_n$ in insertion order. If $n=0$, there is no key line.

Output

The first line contains the preorder traversal.

The second line contains the inorder traversal.

Separate keys on the same line by one space. If the tree is empty, print EMPTY on both lines.

Subtasks

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

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

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

In all subtasks, every $a_i$ is a signed 64-bit integer: $-2^{63}\le a_i\le 2^{63}-1$. Duplicate keys are ignored.

Examples

Input

7
8 3 10 1 6 14 4

Output

8 3 1 6 4 10 14
1 3 4 6 8 10 14

Explanation

Key $8$ becomes the root. Keys $3$ and $10$ become its left and right children, and the remaining keys are inserted according to the same rule.

Preorder visits the root first and gives 8 3 1 6 4 10 14. Inorder visits left subtree, root, then right subtree and gives 1 3 4 6 8 10 14.