(()
or )()
. Your job is to insert some amount of (
or )
into the sequence of brackets in order to balance it.
A balanced bracket is a pair of brackets such that (
is completed by )
. Examples of balanced brackets are ()
, (())
, and (()())
.
You are to find the shortest balanced bracket sequence that can be obtained. If there is more than one such sequence, then output the lexicographically smallest one.
Note: we compare lexicographically smaller such that (
)
.
Constraints
- , is the size of the initial sequence given
- , is the size of the sequence
- may only consist of the characters
(
and)
.
Input Specification
The first line of input will contain a single integer, .
The second line of input will contain a sequence of characters (
and )
, .
Output Specification
Output, on a single line, the lexicographically smallest balanced bracket sequence that can be made.
Sample Input 1
6
(()(((
Sample Output 1
(()((())))
Sample Input 2
9
))()()))(
Sample Output 2
(((())()()))()
Comments