30751번 - Вупсень и Пупсень 다국어

Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности. Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Нет ничего удивительного в том, что они решили объединиться и подготовить очень сложную задачу на поиск наибольшей общей правильной скобочной подпоследовательности.

Подпоследовательностью строки $a$ называется такая строка $b$, которую можно получить удалением из строки $a$ символов на каких-либо (возможно, никаких) позициях.

Последовательность круглых скобок называется правильной в следующих случаях:

1. Если она пустая.
2. Если она состоит из правильной скобочной последовательности, заключённой в скобки.
3. Если она состоит из двух правильных скобочных последовательностей, записанных одна за другой.

Вам даны две строки $s$ и $t$, состоящие из круглых открывающих и закрывающих скобок. Найдите правильную скобочную последовательность $w$ максимальной длины, являющуюся подпоследовательностью строк $s$ и $t$.

Две строки $s$ и $t$ из круглых скобок, длины которых не превосходят $n$ ($1 \leq n \leq 700$), по одной в строке. Любая из строк (в том числе обе) может быть пустой.

Выведите одну строку $w$ --- наибольшую общую правильную скобочную подпоследовательность исходных строк $s$ и $t$. Если таких строк несколько, разрешается вывести любую из них.