Problem Description

You are given a string $ S $ consisting of lowercase English letters a to z, (, and ). For any strings $ a $ and $ b $, $ a+b $ denotes the concatenation of $ a $ and $ b $ in this order. Also, for any string $ a $, $ rev(a) $ denotes the reversed string of $ a $. Output the final string $ S $ after repeating the following operation until no more operations can be performed:

• When a substring of the form ( $ +a+ $ ) exists in $ S $ where $ a $ is a string that does not contain ( or ) (it can be an empty string), replace that substring with $ a+rev(a) $.

It is guaranteed that the string $ S $ has correct parentheses, meaning that the final string $ S $ will not contain ( or ). It can also be shown that the final string is uniquely determined under these conditions.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the final string $ S $ after repeating the operations until no more operations can be performed.

Sample Input and Output

Sample Input #1

(ab)c

Sample Output #1

abbac

Sample Input #2

past

Sample Output #2

past

Sample Input #3

(d(abc)e)()

Sample Output #3

dabccbaeeabccbad

Notes/Hints

Constraints

• $ S $ is a string of length between $ 1 $ and $ 1000 $ consisting of lowercase English letters a to z, (, and ).
• $ S $ contains at least one lowercase English letter.
• The length of the final string $ S $ after all operations is at most $ 1000 $ and does not contain ( or ).

Sample Explanation 1

Replace (ab) with ab $ +rev( $ ab $ ) $ which is abba, then $ S $ becomes abbac. No more operations can be performed, so output this.

Sample Explanation 2

There might be no parentheses in the string.

Sample Explanation 3

There might be empty strings inside the parentheses.

见题面 Input 部分

见题面 Output 部分