Послідовність дужок

Визначимо правильну дужкову послідовність наступним чином:

1. Порожня послідовність є правильною послідовністю.

2. Якщо $S$ є правильною послідовністю, тоді ($S$) і [$S$] є правильними послідовностями.

3. Якщо $A$ і $B$ є правильними послідовностями, тоді $AB$ є правильною послідовністю.

Наприклад, всі наступні послідовності символів є правильними дужковими послідовностями:

()

[]

(())

([])

()[]

()[()]

, , , , ,

І всі наступні послідовності символів не є правильними:

(

[

)

)(

([)]

([(]

, , , , ,

Задано деяку послідовність символів '(', ')', '[', і ']'. Вам потрібно знайти найкоротшу можливу правильну дужкову послідовність, яка містить задану послідовність символів як підпослідовність. Тут рядок a_1 a_2 \ldots a_n називається підпослідовністю рядка b_1 b_2 \ldots b_m, якщо існують такі індекси 1 \le i_1 < i_2 < \ldots < i_n \le m, що a_j = b_{i_j} для всіх 1 \le j \le n.