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.math.BigInteger;
import java.util.*;

// written by luchy0120

public class Main {
    public static void main(String[] args) throws Exception {

        new Main().run();
    }


//    int get_room(int i,int j){
//        return i/3*3 + j/3;
//    }

//    int a[][] = new int[9][9];
//    int space = 0;
//
//    boolean vis_row[][] = new boolean[9][10];
//    boolean vis_col[][] = new boolean[9][10];
//    boolean vis_room[][] = new boolean[9][10];
//    int val[][][] =new int[9][9][];
//    int prepare[][];
//
//    void dfs(int rt){
//
//    }
    char[] s1;
    int l1;

    char[] s2;
    int l2;
    int dp[][][];

    int go(int p1,int p2,int open){
        int ma =  1000000000;
        if(open>l1+l2) return ma;
        if(dp[p1][p2][open]>0) return dp[p1][p2][open];

        if(p1<l1&&p2<l2){

                if ('(' == s1[p1] && '(' == s2[p2]) {
                    ma = Math.min(ma, 1 + go(p1 + 1, p2 + 1, open + 1));
                } else if ('(' == s1[p1]) {
                    ma = Math.min(ma,1 + go(p1 + 1, p2, open + 1));
                } else if ('(' == s2[p2]) {
                    ma = Math.min(ma, 1 + go(p1, p2 + 1, open + 1));
                } else {
                    ma = Math.min(ma, 1 + go(p1, p2, open + 1));
                }

                if(open>0){

                    if (')' == s1[p1] && ')' == s2[p2]) {
                        ma = Math.min(ma, 1 + go(p1 + 1, p2 + 1, open - 1));
                    } else if (')' == s1[p1]) {
                        ma = Math.min(ma, 1 + go(p1 + 1, p2, open - 1));
                    } else if (')' == s2[p2]) {
                        ma = Math.min(ma, 1 + go(p1, p2 + 1, open - 1));
                    } else {
                        ma = Math.min(ma, 1 + go(p1, p2, open - 1));
                    }

                }


        }else if(p1<l1){

            if ('(' == s1[p1]) {
                ma = Math.min(ma, 1 + go(p1 + 1, p2, open + 1));
            }else{
                ma = Math.min(ma, 1 + go(p1 , p2, open + 1));
            }
            if(open>0){
                if (')' == s1[p1]) {
                    ma = Math.min(ma, 1 + go(p1 + 1, p2, open - 1));
                }else{
                    ma = Math.min(ma, 1 + go(p1 , p2, open - 1));
                }
            }

        }else if(p2<l2){

            if ('(' == s2[p2]) {
                ma = Math.min(ma, 1 + go(p1 , p2+1, open + 1));
            }else{
                ma = Math.min(ma, 1 + go(p1 , p2, open + 1));
            }
            if(open>0){
                if (')' == s2[p2]) {
                    ma = Math.min(ma, 1 + go(p1 , p2+1, open - 1));
                }else{
                    ma = Math.min(ma, 1 + go(p1 , p2, open - 1));
                }
            }
        }else if(open> 0){
            ma = Math.min(ma, 1 + go(p1 , p2, open - 1));
        }else{
            ma  = 0;
        }
        return dp[p1][p2][open] = ma;

    }



    void solve(){



         s1 = ns().toCharArray();
        s2 = ns().toCharArray();
        l1 = s1.length;
        l2 = s2.length;
        dp = new int[l1+1][l2+1][l1+l2+1];
        int s = go(0,0,0);

        int p1 = 0;
        int p2 = 0;
        int open = 0;

        int len = dp[0][0][0];

        StringBuilder sb  =new StringBuilder();

        while(len>0) {
            int np1 = p1;
            int np2 = p2;
            int nopen = open;


            if (p1 < l1 && s1[p1] == '(') {
                np1 = p1 + 1;
            }
            if (p2 < l2 && s2[p2] == '(') {
                np2 = p2 + 1;
            }
            nopen = open + 1;
            if (dp[np1][np2][nopen] == len - 1) {
                p1 =np1;p2 = np2;open = nopen; len--; sb.append('(');continue;
            }

             np1 = p1;
             np2 = p2;


            if(open>0) {
                if (p1 < l1 && s1[p1] == ')') {
                    np1 = p1 + 1;
                }
                if (p2 < l2 && s2[p2] == ')') {
                    np2 = p2 + 1;
                }
                nopen = open - 1;
                if (dp[np1][np2][nopen] == len - 1) {
                    p1 =np1;p2 = np2;open = nopen; len--; sb.append(')');continue;
                }
            }
        }
        println(sb);


















    }
    public static String roundS(double result, int scale){
        String fmt = String.format("%%.%df", scale);
        return String.format(fmt, result);
    }








//    void solve() {
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                int v = ni();
//                a[i][j] = v;
//                if(v>0) {
//                    vis_row[i][v] = true;
//                    vis_col[j][v] = true;
//                    vis_room[get_room(i, j)][v] = true;
//                }else{
//                    space++;
//                }
//            }
//        }
//
//
//        prepare = new int[space][2];
//
//        int p = 0;
//
//        for(int i=0;i<9;++i) {
//            for (int j = 0; j < 9; ++j) {
//                if(a[i][j]==0){
//                    prepare[p][0] = i;
//                    prepare[p][1]= j;p++;
//                    List<Integer> temp =new ArrayList<>();
//                    for(int k=1;k<=9;++k){
//                        if(!vis_col[j][k]&&!vis_row[i][k]&&!vis_room[get_room(i,j)][k]){
//                            temp.add(k);
//                        }
//                    }
//                    int sz = temp.size();
//                    val[i][j] = new int[sz];
//                    for(int k=0;k<sz;++k){
//                        val[i][j][k] = temp.get(k);
//                    }
//                }
//            }
//        }
//        Arrays.sort(prepare,(x,y)->{
//           return Integer.compare(val[x[0]][x[1]].length,val[y[0]][y[1]].length);
//        });
//        dfs(0);
//
//
//
//
//
//
//
//
//
//
//    }




    InputStream is;
    PrintWriter out;

    void run() throws Exception {
        is = System.in;
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private char ncc() {
        int b = readByte();
        return (char) b;
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private String nline() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[][] nm(int n, int m) {
        char[][] a = new char[n][];
        for (int i = 0; i < n; i++) a[i] = ns(m);
        return a;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    void print(Object obj) {
        out.print(obj);
    }

    void println(Object obj) {
        out.println(obj);
    }

    void println() {
        out.println();
    }

    void printArray(int a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }

    void printArray(long a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }
}