Memory Cell

Taeyang has to compute a very complex expression on his calculator. He wants to use the calculator's memory, but the model is old and has only one memory cell. To get the most out of that single cell, he looks for the largest common subexpression of the given expression.

Look at the following expression.

$1 + (2 \times 3) + 5 / (1 + 2 \times 3)$

$2 \times 3$ occurs twice here, so it is a common subexpression. $1 + 2 \times 3$ also occurs twice. This expression therefore has two common subexpressions, $2 \times 3$ and $1 + 2 \times 3$, and the largest of them is $1 + 2 \times 3$. The first pair of parentheses, $(2 \times 3)$, is superfluous. Operator precedence makes $1 + (2 \times 3)$ the same expression as $1 + 2 \times 3$. Taeyang wants to find a largest common subexpression and store its value in the single memory cell. Write a program that finds the largest common subexpression of a given expression.

To keep the problem simple, only four binary operators are considered: addition +, subtraction -, multiplication *, and division /. The usual precedence rules apply, so multiplication and division bind tighter than addition and subtraction, and every operator is left associative. The expression tree for the expression above is the one in Figure 1.

Figure 1. The expression tree for $1 + (2 \times 3) + 5 / (1 + 2 \times 3)$.

When you build the expression tree, respect the precedence and the associativity of the operators (Rule 1), and keep the order of the operands of the input expression, so the order in the expression is the same as the in-order traversal of the tree (Rule 2). The expression tree is an ordered, single-rooted tree. A subexpression corresponds to a unique subtree whose leaf nodes represent the operands in the same order as they occur in the expression. A common subexpression therefore exists when the expression tree contains two disjoint identical subtrees. The two occurrences of a common subexpression must not overlap (Rule 3). Rule 3 follows from Rule 1, and it is written out separately for clarity.

The size of an expression is the number of operators and operands in it, which equals the number of nodes of the expression tree. Parentheses written to clarify the binding between operators and operands are not counted. For instance, the size of $(50 + 50) \times ((2) + 3)$ is seven even though it contains several pairs of parentheses. A common subexpression has to be proper, so its size is smaller than the size of the whole expression. Finding a largest common subexpression is thus the same as finding two identical subtrees of maximum size that satisfy Rule 1, Rule 2, and Rule 3.

Consider the expression $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$. You may think that its largest common subexpression is $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$, but the two occurrences of that overlap, which breaks Rule 3. You may also think of $(1 + 1) \times (1 + 1)$, and it is not a common subexpression either, because the expression tree in Figure 2 holds no two disjoint identical subtrees for it. The only common subexpression of the given expression is $1 + 1$, so that one is the largest.

Figure 2. The expression tree for $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$.

As a final example, the common subexpression of $(1 + 2 \times 3) + 5 / (2 \times 3 + 1)$ is $2 \times 3$, not $1 + 2 \times 3$ and not $2 \times 3 + 1$, because the operands of those two come in a different order, which breaks Rule 2.

The first line holds one expression. It consists of operands (positive integers), the binary operators +, -, *, /, and parentheses. The length of the input line is at most 1,000 including the newline character. Multiplication is written * instead of $\times$. Zero or more white spaces can separate the operators, the operands, and the parentheses.

If the given line is a valid expression, assume it contains at least one common subexpression whose size is three or more.

Print the postfix of the largest common subexpression on a single line. The postfix of an expression is the result of the post-order traversal of its expression tree. For instance, the postfix of 1 + 2 * 3 is 1 2 3 * +. Separate the operators and the operands with one space.

If several different largest common subexpressions exist, print only the one whose postfix string comes first in lexicographic order. Characters compare by their ASCII value, so a space (32) comes before * (42), + (43), - (45), / (47), and the digits 0 (48) through 9 (57).

If the input is not a valid expression, print ERROR.