Задача №685. Скобки(3)

Определим правильные скобочные выражения так:

  1. Пустое выражение - правильное.
  2. Если выражение S правильное, то (S) и [S] также правильные.
  3. Если выражения A и B правильные, то и выражение AB - правильное.

Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные

В первой строке находятся символы (, ), [ и ] без пробелов.

Выходные данные

Выводится искомая последовательность скобок без пробелов.

Сдать: для сдачи задач необходимо войти в систему