Description

Given an arithmetic expression, some parts are enclosed in parentheses to show different precedence. You need to delete some pairs of matching parentheses, and output all possible deletion schemes. Output the results in lexicographical order.

For example, given the expression (2+(2*2)+2), all valid results are (2+2*2+2) 2+(2*2)+2 2+2*2+2. However, (2+2*2)+2 and 2+(2*2+2) are not valid, because the deleted parentheses are not removed as matching pairs.

Input Format

One line containing an arithmetic expression.

Output Format

Output all distinct arithmetic expressions that can be obtained by deleting valid pairs of parentheses. Output them in lexicographical order.

(0/(0))

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

(2+(2*2)+2)

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

(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

Hint

Constraints

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

Notes

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

Translated by ChatGPT 5