# Brackets sequence

# Brackets sequence

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**AB**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 **]** are given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string `a`

is called a subsequence of the string _{1}a_{2}...a_{n}`b`

, if there exist such indices _{1}b_{2}...b_{m}**1** ≤ `i`

< _{1}`i`

< ... < _{2}`i`

≤ _{n}**m** that `a`

= _{j}`b`

for all _{ij}**1** ≤ **j** ≤ **n**.

#### 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.

([(]

()[()]