Given n number each representing value of a node, construct a tree in the following manner:

1. Let's say node to be inserted has value x
2. If x is less than or equal to value of the current root node then  insert to the left of the current root
3. If x is greater than the value of the current root then insert node in the right of this node

The above insertion will make a special tree known as Binary Search Tree. Print the resulting tree using following traversals:

1. Inorder
2. Preorder
3. Postorder

Input Format:

First line of input contains an integer n i.e. number of nodes. Second line contains n space separate integers.

Output Format:

Print the tree in inorder, preoder, postorder traversal (follow the order). After each travesal print a newline.

Constraints:

All the numbers are well with in the integer range.