Trees

Trees appear very often in computer science. Unlike trees in nature, computer-science trees grow upside down: the root is at the top and the leaves are at the bottom.

A tree is made of nodes. One node is the root. Every node $w$ other than the root has exactly one father $v$; if $v$ is the father of $w$, then $w$ is a son of $v$. A node with no sons is a leaf. The sons of a node $w$, their sons, their sons' sons, and so on are the descendants of $w$. Every node except the root is a descendant of the root.

Each node has a level number. The root has level $0$, and a son's level is one greater than its father's.

A tree is a complete binary tree exactly when every node has either two sons or no sons at all. In a binary tree the two sons are called left and right.

The picture below shows a complete binary tree. Its nodes are numbered in preorder: the root gets number $1$, a father comes before its sons, and the left son together with all of its descendants gets smaller numbers than the right son together with all of its descendants.

A complete binary tree with such a numbering can be written down in several ways. Three of them follow.

Genealogical representation.\ A sequence of numbers. The first element is $0$, and for $j > 1$ the $j$-th element is the number of the father of node $j$.

Bracket representation.\ Each node maps to a string of brackets. A leaf maps to (). Any other node $w$ maps to (lr), where l and r are the strings of the left and right sons of $w$. The string of the root is the bracket representation of the whole tree.

Level representation.\ The sequence of the level numbers of the leaves, listed in the node-numbering order described above.

The tree in the picture can be described as follows.

Read a sequence of numbers and decide whether it is the level representation of some complete binary tree. If it is not, print the single word NIE ("no"). If it is, output the two other representations of that tree: the genealogical one and the bracket one.

The first line contains a positive integer $m$ ($m \le 2500$), the number of elements in the sequence. The second line contains those $m$ elements separated by single spaces.

The input is always given in a correct format, so your program does not need to check it.

Print one of the following:

• the single word NIE, or
• two lines: the first line holds the genealogical representation with its elements separated by single spaces, and the second line holds the bracket representation as a string of ( and ) characters with no spaces.