Вам задано две скобочные последовательности (не обязательно правильные) \(s\) и \(t\), состоящие только из символов '(' и ')'. Вы хотите построить кратчайшую правильную скобочную последовательность, которая содержит обе заданные скобочные последовательности в качестве подпоследовательностей (не обязательно подряд идущих).
Напомним, что такое правильная скобочная последовательность:
- () является правильной скобочной последовательностью;
- если \(S\) является правильной скобочной последовательностью, то (\(S\)) является правильной скобочной последовательностью;
- если \(S\) и \(T\) являются правильными скобочными последовательностями, то \(ST\) (конкатенация \(S\) и \(T\)) тоже является правильной скобочной последовательностью.
Напомним, что подпоследовательностью строки \(s\) называется такая строка \(t\), которая получается из \(s\) при помощи удаления некоторого (возможно, нулевого) количества символов. Например, «coder», «force», «cf» и «cores» являются подпоследовательностями «codeforces», а «fed» и «z» — нет.
Выходные данные
Выведите одну строку — кратчайшую правильную скобочную последовательность, которая содержит обе заданные скобочные последовательности как подпоследовательности (не обязательно подряд идущие). Если существует несколько возможных ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
(())(()
()))()
|
(())()()
|
|
2
|
)
((
|
(())
|
|
3
|
)
)))
|
((()))
|
|
4
|
())
(()(()(()(
|
(()()()(()()))
|