Problem Description

Define the following rules:

1. An empty string is a "balanced bracket sequence".
2. If string $S$ is a "balanced bracket sequence", then $\texttt{[}S\texttt]$ and $\texttt{(}S\texttt)$ are also "balanced bracket sequences".
3. If strings $A$ and $B$ are both "balanced bracket sequences", then $AB$ (concatenation of the two strings) is also a "balanced bracket sequence".

For example, the following strings are balanced bracket sequences:

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

While the following are not:

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

Given a string $s$ consisting only of (, ), [, and ], you are asked to pair each character in the string according to the following method:

1. Scan the string from left to right.
2. For the current character, if it is a right bracket, look at the nearest unmatched left bracket to its left. If the left bracket corresponds to it (i.e., a parenthesis matches a parenthesis, and a square bracket matches a square bracket), pair them. If there is no unmatched left bracket to its left or it does not correspond, the pairing fails.

After pairing, for all unmatched brackets in $s$, add a character next to it to make the bracket and the new character a pair.

Input Format

The input consists of a single line containing the string $s$.

Output Format

Output a single line containing the resulting string.

Sample Input and Output

Sample Input #1

([()

Sample Output #1

()[]()

Sample Input #2

([)

Sample Output #2

()[]()

Notes

Data Constraints

For all test cases, the length of $s$ is guaranteed to be no more than $100$, and it only contains the characters (, ), [, and ].

见题面 Input 部分

见题面 Output 部分