Hide

Problem D
Zagrade

Mirko was bored at his chemistry class, so he played Bomb Switcher on his cell phone. Unfortunately, he was spotted and was given a ridiculously heavy assignment for homework. For a given valid math expression with brackets, he must find all different expressions that can be obtained by removing valid pairs of brackets from the original expression. Two expressions are different if there is a character at which they differ.

For example, given $(2+(2*2)+2)$, one can get $(2+2*2+2)$, $2+(2*2)+2$, and $2+2*2+2$. $(2+2*2)+2$ and $2+(2*2+2)$ can’t be reached, since we would have to remove pairs of brackets that are not valid. More than one pairs of brackets can surround the same part of the expression.

Input

The first and only line of input contains one valid mathematical expression composed of nonnegative integers, basic arithmetic operations denoted with characters ‘+’, ‘*’, ‘-’ and ‘/’, and brackets ‘(’ and ‘)’.

Given expression doesn’t have more than 200 characters, and will have at least one, and no more than 10 pairs of brackets. Each expression is guaranteed to have at least one pair of brackets.

Output

Output all different expressions that can be obtained by removing valid pairs of brackets, sorted lexicographically.

Sample Input 1 Sample Output 1
(0/(0))
(0/0)
0/(0)
0/0
Sample Input 2 Sample Output 2
(2+(2*2)+2)
(2+2*2+2)
2+(2*2)+2
2+2*2+2
Sample Input 3 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)
1+2*3+4

Please log in to submit a solution to this problem

Log in