F. Две скобочные последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано две скобочные последовательности (не обязательно правильные) $$$s$$$ и $$$t$$$, состоящие только из символов '(' и ')'. Вы хотите построить кратчайшую правильную скобочную последовательность, которая содержит обе заданные скобочные последовательности в качестве подпоследовательностей (не обязательно подряд идущих).

Напомним, что такое правильная скобочная последовательность:

  • () является правильной скобочной последовательностью;
  • если $$$S$$$ является правильной скобочной последовательностью, то ($$$S$$$) является правильной скобочной последовательностью;
  • если $$$S$$$ и $$$T$$$ являются правильными скобочными последовательностями, то $$$ST$$$ (конкатенация $$$S$$$ и $$$T$$$) тоже является правильной скобочной последовательностью.

Напомним, что подпоследовательностью строки $$$s$$$ называется такая строка $$$t$$$, которая получается из $$$s$$$ при помощи удаления некоторого (возможно, нулевого) количества символов. Например, «coder», «force», «cf» и «cores» являются подпоследовательностями «codeforces», а «fed» и «z» — нет.

Входные данные

Первая строка входных данных содержит одну скобочную последовательность $$$s$$$, состоящую из не более $$$200$$$ символов '(' и ')'.

Вторая строка входных данных содержит одну скобочную последовательность $$$t$$$, состоящую из не более $$$200$$$ символов '(' и ')'.

Выходные данные

Выведите одну строку — кратчайшую правильную скобочную последовательность, которая содержит обе заданные скобочные последовательности как подпоследовательности (не обязательно подряд идущие). Если существует несколько возможных ответов, выведите любой.

Примеры
Входные данные
(())(()
()))()
Выходные данные
(())()()
Входные данные
)
((
Выходные данные
(())
Входные данные
)
)))
Выходные данные
((()))
Входные данные
())
(()(()(()(
Выходные данные
(()()()(()()))