Вупсень и Пупсень

문제

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

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

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

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

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

입력

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

출력

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