Problem Description

You are given a string containing only left parentheses ( and right parentheses ), but the parentheses are not properly paired. To make the string look better, you want to insert the minimum number of parentheses (you can insert any number of parentheses at any position, but you cannot change the existing ones) to make the modified string have properly paired parentheses.

Input Format

Input consists of a single line containing a string, which is a sequence of parentheses that are not all properly paired.

Output Format

Output a single line, which is the string after inserting parentheses to make it properly paired. If there are multiple shortest solutions, output any one of them.

Sample Input and Output

Sample Input #1

(())()(

Sample Output #1

(())()()

Sample Input #2

))((

Sample Output #2

(())()()

Notes

For 60% of the data, the length of the input string does not exceed 10.

For 100% of the data, the length of the input string does not exceed 10^3.

The original full score for this problem was 15 points.

见题面 Input 部分

见题面 Output 部分