Hopefully Educational Rounds #1

Start

2019-08-08 07:20 UTC

Hopefully Educational Rounds #1

End

2019-08-15 07:20 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -44 days 1:57:26

Time elapsed

168:00:00

Time remaining

0:00:00

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