Определим правильные скобочные выражения так:
Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.
Ограничения: исходная последовательность содержит не более 100 скобок.
Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.
Выходные данные
Выводится искомая последовательность скобок без пробелов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
([(] |
()[()] |
| 2 |
( |
() |