eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Скобочная последовательность

Скобочная последовательность

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Определим правильное скобочное выражение следующим образом:

  1. Пустое выражение - правильное.

  2. Если выражение S правильное, то (S) и [S] также правильные.

  3. Если выражения A и B правильные, то и выражение AB правильное.

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

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

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

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

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

Пример

Входные данные #1
([(]
Выходные данные #1
()[()]