Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности. Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Нет ничего удивительного в том, что они решили объединиться и подготовить очень сложную задачу на поиск наибольшей общей правильной скобочной подпоследовательности.
Подпоследовательностью строки a называется такая строка b, которую можно получить удалением из строки a символов на каких-либо (возможно, никаких) позициях.
Последовательность круглых скобок называется правильной в следующих случаях:
Вам даны две строки s и t, состоящие из круглых открывающих и закрывающих скобок. Найдите правильную скобочную последовательность w максимальной длины, являющуюся подпоследовательностью строк s и t.
Две строки s и t из круглых скобок, длины которых не превосходят n (1 ≤ n ≤ 700), по одной в строке. Любая из строк (в том числе обе) может быть пустой.
Выведите одну строку w — наибольшую общую правильную скобочную подпоследовательность исходных строк s и t. Если таких строк несколько, разрешается вывести любую из них.
())(()()()
)(())(())
(())()
))((
(())
