Bracket Pairing and Completion

Given a string s consisting solely of the characters (, ), [, and ], perform the following process to pair the brackets:

1. Scan the string from left to right.
2. When a right bracket is encountered (i.e. ) or ]), consider the nearest unmatched left bracket to its left. If this left bracket matches the current right bracket (i.e. ( matches ) and [ matches ]), pair them and mark both as matched. Otherwise, the right bracket remains unmatched.
3. After scanning the entire string, for every unmatched bracket in s (whether it is a left bracket or a right bracket), add a single bracket adjacent to it so that they form a matching pair. Specifically, for an unmatched left bracket, insert its matching right bracket immediately after it, and for an unmatched right bracket, insert its matching left bracket immediately before it.

A string is considered a balanced bracket sequence if it can be generated by the following rules:

• The empty string is a balanced bracket sequence.
• If S is a balanced bracket sequence, then both \( (S) \) and \( [S] \) are balanced bracket sequences.
• If A and B are balanced bracket sequences, then the concatenation \( AB \) is also a balanced bracket sequence.

For example, the following strings are balanced:

• ()
• []
• (())
• ([])
• ()[]
• ()[()]

While these strings are not balanced:

• (
• [
• ]
• )(
• ())
• ([()

Your task is to process the given string according to the pairing method described above and output the final corrected bracket sequence which becomes balanced.

inputFormat

The input consists of a single line containing the string s which is composed only of the characters (, ), [, and ].

outputFormat

Output the corrected bracket sequence after performing the pairing process and inserting the necessary brackets. The resulting sequence must be balanced as defined in the problem statement.

sample

()

()