题目描述

Vupsen 非常喜欢出寻找最长公共子序列的题。Pupsen 非常喜欢出寻找最长合法括号子序列的题。因此，他们决定联合起来，准备一道非常困难的题：寻找最长公共合法括号子序列。

字符串 $a$ 的子序列是指可以通过删除 $a$ 中若干个位置上的字符（也可以一个都不删）得到的字符串 $b$。

圆括号序列在以下情况下称为合法括号序列：

1. 它是空串。
2. 它由某个合法括号序列外面再套一对括号得到。
3. 它由两个合法括号序列首尾相接得到。

给定两个只由圆括号 ( 和 ) 组成的字符串 $s$ 和 $t$。请找出一个长度最大的合法括号序列 $w$，使得 $w$ 同时是字符串 $s$ 和 $t$ 的子序列。

输入格式

输入包含两行，分别为由圆括号组成的字符串 $s$ 和 $t$。两个字符串的长度都不超过 $n$（$1 \le n \le 700$）。任意一个字符串（包括两个字符串）都可能为空。

输出格式

输出一行字符串 $w$，表示原字符串 $s$ 和 $t$ 的最长公共合法括号子序列。如果存在多个答案，输出任意一个均可。

样例 1

输入

())(()()()
)(())(())

输出

(())()

样例 2

输入

))((
(())

输出

样例 2 的输出为空串。

评分方式

测试点分为四组。只有通过某一组的全部测试，以及所有之前组的全部测试，才能获得该组分数。