Description

Parentheses are at the heart of programming.
    Understand parentheses and you can rule the earth.
        by Mike James

To construct a unique binary search tree, the in-order and pre/post-order traversal sequences are both required.
However, it takes too much memory in some applications.
Mike came up with a genius solution: use parentheses to represents a unique binary tree.
A tree can be represented like: Tree = ( data LeftSubTree RightSubTree ) if the data exisit. Otherwise, Tree = () which means the tree contains nothing.

For example:

1. () = NULL
2. (3()())
   
3. (2(1()())(3()())):
   
4. (1()(2()(3()()))):
   

Given a valid parentheses tree expression.
Your task is to bulid the tree from it, and output the inorder and postorder traversal sequences. Then you can rule the earth.

Input

The first line contains N, denoting the length of parentheses expression.
The second line contains the parentheses representation for a unique tree.
It is guaranteed that:

• 2 ≤ N ≤ 10⁶
• The number of each Node is in the range of int.

Output

Output the in-order and post-order traversal sequence for the tree on the first and second line.
Every number is followed by one space.
Remember '\n' on the end of each line.

Tree of Sample IO

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss