A routing string is made of lowercase English letters and balanced parentheses. Starting from the innermost pair of parentheses and working outward, repeatedly reverse the substring enclosed by a matching pair of parentheses and remove those parentheses. Continue until no parentheses remain. Print the final string, which contains only lowercase letters.
Input format
Line 1: a non-empty string of lowercase English letters and the characters ( and ), with all parentheses balanced.
Output format
A single line: the resulting string after all parenthesized sections have been reversed and the parentheses removed. (This may be empty if the input contains only parentheses.)
Constraints
- 1 <= length of the string <= 2000
- Parentheses are balanced and properly nested.
- Apart from parentheses, all characters are lowercase English letters.