Three DFS Traversals and Level Order

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.

Print four traversals of the same resulting tree:

• preorder: root, left, right;
• inorder: left, root, right;
• postorder: left, right, root;
• level-order: visit nodes level by level from top to bottom; for each node, its left child is considered before its right child.

Input

The first line contains $n$.

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

Output

Print exactly four lines:

Line 1: preorder.

Line 2: inorder.

Line 3: postorder.

Line 4: level-order.

Keys on one line are separated by one space. If the tree is empty, all four lines must be EMPTY.

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, $-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
1 4 6 3 14 10 8
8 3 10 1 6 14 4

Explanation

Key $8$ is the root, with $3$ and $10$ as its children. The four output lines are respectively the preorder, inorder, postorder, and level-order traversals of this same tree.