Problem: You are given two bracket sequences (not necessarily regular) s and t consisting only of characters '(' and ')'. You want to construct the shortest regular bracket sequence that contains both given bracket sequences as subsequences (not necessarily contiguous).

Recall what is the regular bracket sequence:

  * () is the regular bracket sequence; 
  * if S is the regular bracket sequence, then (S) is a regular bracket sequence; 
  * if S and T regular bracket sequences, then ST (concatenation of S and T) is a regular bracket sequence. 



Recall that the subsequence of the string s is such string t that can be obtained from s by removing some (possibly, zero) amount of characters. For example, "coder", "force", "cf" and "cores" are subsequences of "codeforces", but "fed" and "z" are not.

Input

The first line of the input contains one bracket sequence s consisting of no more than 200 characters '(' and ')'.

The second line of the input contains one bracket sequence t consisting of no more than 200 characters '(' and ')'.

Output

Print one line — the shortest regular bracket sequence that contains both given bracket sequences as subsequences (not necessarily contiguous). If there are several answers, you can print any.

Examples

Input


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


Output


(())()()


Input


)
((


Output


(())


Input


)
)))


Output


((()))


Input


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


Output


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

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

/*
───────────────■■■─────────────────────────
──█▄─▄█─▄▀▀▀▄─█──▄█─────█──▄▀─▄▀▀▀▄─▀▀█▀▀──
──█─▀─█─█───█─█─█─█─────█■█───█───█───█────
──█───█─▀▄▄▄▀─█▀──█─────█──▀▄─▀▄▄▄▀───█────
───────────────────────────────────────────
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int INF = (int) 1e9;
    static final int N = 202;
    static char[] s, t;
    static int[][][] dp;
    static Par[][][] par;

    static class Par {
        int i, j, k;
        char ch;

        Par(int i, int j, int k, char ch) {
            this.i = i;
            this.j = j;
            this.k = k;
            this.ch = ch;
        }
    }

    static void solve() {
        s = in.next().toCharArray();
        t = in.next().toCharArray();

        dp = new int[N][N][N];
        for (int i = 0; i <= s.length; i++) {
            for (int j = 0; j <= t.length; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }
        par = new Par[N][N][N];
        dp[0][0][0] = 0;
        for (int k = 1; k < N; k++) {
            dp[0][0][k] = k;
            par[0][0][k] = new Par(0, 0, k - 1, '(');
            //
        }

        for (int i = 0; i <= s.length; i++) {
            for (int j = 0; j <= t.length; j++) {
                for (int k = 0; k < N; k++) {
                    if (i > 0 && j > 0) {
                        if (s[i - 1] == t[j - 1]) {
                            if (s[i - 1] == '(') {
                                if (k > 0) {
                                    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
                                    par[i][j][k] = new Par(i - 1, j - 1, k - 1, '(');
                                }
                            } else {
                                if (k < N - 1) {
                                    dp[i][j][k] = dp[i - 1][j - 1][k + 1] + 1;
                                    par[i][j][k] = new Par(i - 1, j - 1, k + 1, ')');
                                }
                            }
                        } else {
                            if (s[i - 1] == '(') {
                                if (k > 0 && k < N - 1) {
                                    if (dp[i - 1][j][k - 1] + 1 <= dp[i][j - 1][k + 1] + 1) {
                                        dp[i][j][k] = dp[i - 1][j][k - 1] + 1;
                                        par[i][j][k] = new Par(i - 1, j, k - 1, '(');
                                    } else {
                                        dp[i][j][k] = dp[i][j - 1][k + 1] + 1;
                                        par[i][j][k] = new Par(i, j - 1, k + 1, ')');
                                    }
                                } else if (k == 0) {
                                    dp[i][j][k] = dp[i][j - 1][k + 1] + 1;
                                    par[i][j][k] = new Par(i, j - 1, k + 1, ')');
                                } else if (k == N - 1) {
                                    dp[i][j][k] = dp[i - 1][j][k - 1] + 1;
                                    par[i][j][k] = new Par(i - 1, j, k - 1, '(');
                                }
                            } else {
                                if (k > 0 && k < N - 1) {
                                    if (dp[i][j - 1][k - 1] + 1 <= dp[i - 1][j][k + 1] + 1) {
                                        dp[i][j][k] = dp[i][j - 1][k - 1] + 1;
                                        par[i][j][k] = new Par(i, j - 1, k - 1, '(');
                                    } else {
                                        dp[i][j][k] = dp[i - 1][j][k + 1] + 1;
                                        par[i][j][k] = new Par(i - 1, j, k + 1, ')');
                                    }
                                } else if (k == 0) {
                                    dp[i][j][k] = dp[i - 1][j][k + 1] + 1;
                                    par[i][j][k] = new Par(i - 1, j, k + 1, ')');
                                } else if (k == N - 1) {
                                    dp[i][j][k] = dp[i][j - 1][k - 1] + 1;
                                    par[i][j][k] = new Par(i, j - 1, k - 1, '(');
                                }
                            }
                        }
                    } else if (i > 0) {
                        if (s[i - 1] == '(') {
                            if (k > 0) {
                                dp[i][j][k] = dp[i - 1][j][k - 1] + 1;
                                par[i][j][k] = new Par(i - 1, j, k - 1, '(');
                            }
                        } else {
                            if (k < N - 1) {
                                dp[i][j][k] = dp[i - 1][j][k + 1] + 1;
                                par[i][j][k] = new Par(i - 1, j, k + 1, ')');
                            }
                        }
                    } else if (j > 0) {
                        if (t[j - 1] == '(') {
                            if (k > 0) {
                                dp[i][j][k] = dp[i][j - 1][k - 1] + 1;
                                par[i][j][k] = new Par(i, j - 1, k - 1, '(');
                            }
                        } else {
                            if (k < N - 1) {
                                dp[i][j][k] = dp[i][j - 1][k + 1] + 1;
                                par[i][j][k] = new Par(i, j - 1, k + 1, ')');
                            }
                        }
                    }
                }
            }
        }
        int min = dp[s.length][t.length][0], mink = 0;
        Par p = par[s.length][t.length][0];
        for (int k = 1; k < N; k++) {
            if (dp[s.length][t.length][k] + k < min) {
                min = dp[s.length][t.length][k] + k;
                mink = k;
                p = par[s.length][t.length][k];
            }
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < mink; i++) {
            ans.append(')');
        }
        while (p != null) {
            ans.insert(0, p.ch);
            p = par[p.i][p.j][p.k];
        }

//        out.println(min);
        out.println(ans.toString());
    }

    public static void main(String[] args) {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("input.txt"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("output.txt"));


        int q = 1;

        while (q-- > 0) {
            solve();
        }

        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}