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

시간 제한3.5초메모리 제한1024 MB

요약

두 괄호 문자열이 주어질 때, 두 문자열 모두의 부분수열이면서 올바른 괄호열인 가장 긴 문자열을 찾는다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

출력

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

예제2

예제 1
입력
```
())(()()()
)(())(())
```
예상 출력
```
(())()
```
예제 2
입력
```
))((
(())
```
예상 출력