Dr. Podboq, or: How We Became Asymmetric

After studying for a long time how the embryos of organisms become asymmetric during their development, the famous biologist Dr. Podboq has arrived at a new hypothesis. He is now preparing a poster for an upcoming academic conference. The poster shows a tree that represents how an embryo develops from a single cell through repeated cell divisions. Your job is to write a program that transforms such trees into a normalized form so that the audience can grasp the idea more easily.

A tree that represents a process of cell divisions has the form described below.

• The starting cell is drawn as a circle at the top.
• Each cell either stops dividing or divides into exactly two cells. Therefore, every circle (cell) has either no branch going downward, or exactly two branches leading to its two child cells.

(Figure F-1 shows an example of such a tree.)

According to Dr. Podboq's hypothesis, we can tell which cells are more or less asymmetric from the structure of this tree. First, the hypothesis defines the left-right similarity of a cell as follows.

1. The left-right similarity of a cell that never divided is $0$.
2. For a cell that did divide, collect the partial trees rooted at each of its child and descendant cells, and count how many distinct structures occur among them. The left-right similarity of the cell is the ratio of the number of structures that occur on both the left-child side and the right-child side to the total number of distinct structures. Two trees are regarded as having the same structure if one can be turned into exactly the same shape as the other by swapping the two child cells of some chosen cells.

For example, consider the tree below.

(Figure F-2: an example tree.)

The left-right similarity of cell A is computed as follows. Among the descendants of cell B, the left child of A, three distinct structures occur. Note that even though the last of them occurs three times, when counting kinds of structures it is counted only once.

(Figure F-3 shows the structures occurring among the descendants of B.)

Among the descendants of cell C, the right child of A, four distinct structures occur.

(Figure F-4 shows the structures occurring among the descendants of C.)

The first, second, and third structures on the B side are the same as the second, third, and fourth structures on the C side, respectively. Hence there are four distinct structures in total, and three of them are common to both the left and right sides, which means the left-right similarity of A is $3/4$.

Given the left-right similarity of every cell, the hypothesis lets us decide which of two cells X and Y is more asymmetric, using the following rules.

1. If X and Y have different left-right similarities, the one with the lower left-right similarity is more asymmetric.
2. Otherwise, if neither X nor Y has child cells, they are exactly equally asymmetric.
3. Otherwise, both X and Y must have two child cells. Compare the child of X that is more (or equally) asymmetric with the child of Y that is more (or equally) asymmetric; the cell whose such child is more asymmetric is itself more asymmetric.
4. If this is still a tie, compare the remaining, less (or equally) asymmetric child of X with that of Y; the cell whose such child is more asymmetric is itself more asymmetric.
5. If it is still a tie, X and Y are exactly equally asymmetric.

When comparing child cells in the rules above, apply this same set of rules recursively.

Your job is to transform a given cell-division tree, only by swapping the two child cells of chosen cells, into a tree that satisfies the following conditions.

1. For every cell X that is the starting cell of the tree, or a left child of some parent cell: if X has two child cells, the one on the left must be at least as asymmetric as the one on the right.
2. For every cell X that is a right child of some parent cell: if X has two child cells, the one on the right must be at least as asymmetric as the one on the left.

When two child cells are equally asymmetric, their order does not matter, because either order gives a tree of the same shape.

For example, suppose the given tree is the one in Figure F-2. First we compare B and C; because B has the lower left-right similarity, it is more asymmetric, so we keep B on the left and C on the right. Next, because B is a left child of A, we order B's two children so that the more asymmetric one is on the left. Because C is a right child of A, we order C's two children so that the more asymmetric one is on the right. Handling every other cell the same way, the tree is finally transformed into the result shown below.

(Figure F-5 shows the example tree after the transformation.)

Please note that the only operation allowed during the transformation is swapping the two child cells of some parent cell. For instance, you may not transform the tree in Figure F-2 into the one shown in Figure F-6.

The input consists of $n$ lines ($1 \le n \le 100$), each describing one tree, followed by a line that contains only a single $0$, which marks the end of the input. Each tree has at least $1$ and at most $127$ cells. Below is an example of a tree description.

((x (x x)) x)

This description represents the tree shown in Figure F-1. More precisely, a tree description follows one of the two formats below.

"(" <description of the left child tree> <one space> <description of the right child tree> ")"

or

"x"

The former describes a tree whose starting cell has two child cells; the latter describes a tree whose starting cell has no child cell.

For each tree in the input, print one line describing the tree after the transformation. In the output, describe trees using the same format as the input, and print the descriptions in the same order as the input. Each line must contain exactly one tree description and nothing else.