给定两个括号序列(不一定是常规的)$$$s$$$ 和 $$$t$$$,仅由字符“(”和“)”组成。您想要构造最短的常规括号序列,其中包含两个给定的括号序列作为子序列(不一定是连续的)。
回想一下什么是常规括号序列:
- () 是常规括号序列;
- 如果 $$$S$$$ 是常规括号序列,则 ($$$S$$$) 是常规括号序列;
- 如果 $$$S$$$ 和 $$$T$$$ 为常规括号序列,则 $$$ST$$$ ($$$S$$$ 和 $$$T$$$ 的串联)是常规括号序列。
回想一下,字符串 $$$s$$$ 的子序列是这样的字符串 $$$t$$$,可以通过删除一些(可能是零)字符从 $$$s$$$ 获得。例如,“coder”、“force”、“cf”和“cores”是“codeforces”的子序列,但“fed”和“z”不是。
输入
输入的第一行包含一个括号序列 $$$s$$$,由不超过 $$$200$$$ 字符“(”和“)”组成。
输入的第二行包含一个括号序列 $$$t$$$,由不超过 $$$200$$$ 字符“(”和“)”组成。
输出
打印一行 — 最短的常规括号序列,其中包含两个给定的括号序列作为子序列(不一定是连续的)。如果有多个答案,您可以打印任何一个。
示例
输入 #1
(())(() ()))()
输出 #1
(())()()
输入 #2
) ((
输出 #2
(())
输入 #3
) )))
输出 #3
((()))
输入#4
()) (()(()(()(
输出#4
(()()()(()()))