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

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

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

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

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

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

()

[]

(())

([])

()[]

()[()]

, , , , ,

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

(

[

)

)(

([)]

([(]

, , , , ,

Задано деяку послідовність символів '(', ')', '[', і ']'. Вам потрібно знайти найкоротшу можливу правильну дужкову послідовність, яка містить задану послідовність символів як підпослідовність. Тут рядок a_1a_2...a_n називається підпослідовністю рядка b_1b_2...b_m, якщо існують такі індекси 1 ≤ i_1 < i_2 < ... < i_n ≤ m, що a_j=b_ij для всіх 1 ≤ j ≤ n.

Вхідні дані

Вхід містить не більше 100 дужок (символів '(', ')', '[' і ']'), які розташовані на одному рядку без будь-яких інших символів між ними.

Вихідні дані

Напишіть один рядок, що містить деяку правильну дужкову послідовність, яка має мінімально можливу довжину і містить задану послідовність як підпослідовність.

Приклади