Problem Description

Given an arithmetic expression where some parts are enclosed in parentheses to indicate different precedence levels, you are asked to remove some pairs of matching parentheses and output all possible removal schemes. The output should be in lexicographical order.

For example, given the arithmetic expression (2+(2*2)+2), all valid schemes are (2+2*2+2), 2+(2*2)+2, and 2+2*2+2. The schemes (2+2*2)+2 and 2+(2*2+2) are not valid because the removed parentheses pairs do not match.

Input Format

Input consists of a single line containing an arithmetic expression.

Output Format

Output different arithmetic expressions obtained by removing valid pairs of parentheses. The output should be in lexicographical order.

Sample Input and Output

Sample Input #1

(0/(0))

Sample Output #1

(0/0)
0/(0)
0/0

Sample Input #2

(2+(2*2)+2)

Sample Output #2

(2+2*2+2)
2+(2*2)+2
2+2*2+2

Sample Input #3

(1+(2*(3+4)))

Sample Output #3

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

Notes

Data Size and Constraints

For 100% of the data, the length of the given arithmetic expression does not exceed 200, and the input only contains +, -, *, /, (, and ).

Notes

This problem is translated from COCI2011-2012 CONTEST #6 T3 ZAGRADE.

见题面 Input 部分

见题面 Output 部分