Remove Invalid Parenthesis

hard

1. You are given a string, which represents an expression having only opening and closing parenthesis.
2. You have to remove minimum number of parenthesis to make the given expression valid.
3. If there are multiple answers, you have to print all of them.

Note -&gt; Check out the question video and write the recursive code as it is intended without changing signature. The judge can't 
               force you but intends you to teach a concept.

Input Format

A string containing only opening and closing parenthesis

Output Format

Print all the Valid expressions. Check the sample ouput and question video.

Constraints

1 &lt;= length of string &lt;= 20

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

()())()

Output

(())()
()()()

Word Break - I

Largest Number Possible After At Most K Swaps