Последовательность скобок
Определим правильную последовательность скобок следующим образом:
Пустая последовательность считается правильной.
Если S — правильная последовательность, то (S) и [S] также являются правильными последовательностями.
Если 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 скобок (символов '(', ')', '[' и ']'), расположенных в одной строке без других символов.
Выходные данные
Выведите строку, содержащую правильную последовательность скобок минимальной возможной длины, которая включает данную последовательность как подпоследовательность.