Brackets Sequence#3628

Brackets Sequence

1 second

16 megabytes

Easy

Let us define a regular brackets sequence in the following way:

Empty sequence is a regular sequence.
If $S$ is a regular sequence, then ( $S$ ) and [ $S$ ] are both regular sequences.
If $A$ and $B$ are regular sequences, then $A B$ is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:

()

[]

(())

([])

()[]

()[()]

, , , , ,

And all of the following character sequences are not:

(

[

)

)(

([)]

([(]

, , , , ,

Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string $a_{1} a_{2} \dots a_{n}$ a_1 a_2 \ldots a_n is called a subsequence of the string $b_{1} b_{2} \dots b_{m}$ b_1 b_2 \ldots b_m, if there exist such indices $1 \leq i_{1} < i_{2} < \dots < i_{n} \leq m$ 1 \le i_1 < i_2 < \ldots < i_n \le m, that $a_{j} = b_{i_{j}}$ a_j = b_{i_j} for all $1 \leq j \leq n$ 1 \le j \le n.

Input

The input contains at most $100$ brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output

Write a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Examples

Example 1

Loading

a_{1} a_{2} \dots a_{n}

b_{1} b_{2} \dots b_{m}

1 \leq i_{1} < i_{2} < \dots < i_{n} \leq m

a_{j} = b_{i_{j}}

1 \leq j \leq n