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.LinkedList;
import java.util.Scanner;
import java.util.stream.Collector;

@SuppressWarnings("Duplicates")
public class ProblemF {

    public static String s1,s2;
    public static final int INF = Integer.MAX_VALUE/2;
    public static int[][][][] memo = new int[205][205][205][4]; //0 val 1-3 parent
                                // s1 processed, s2 processed, bracket balance

    public static void main(String[] args) throws IOException{
        //Reader sc = new Reader();
        PrintWriter pw = new PrintWriter(System.out);
        //Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 205; i++) {
            for (int j = 0; j < 205; j++) {
                for (int k = 0; k < 205; k++) {
                    memo[i][j][k][0] = INF;
                }
            }
        }
        memo[0][0][0][0] = 0;
        s1 = br.readLine(); int l1 = s1.length();
        s2 = br.readLine(); int l2 = s2.length();

        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                for (int k = 0; k < 203; k++) {
                    if (memo[i][j][k][0]==INF) continue;
                    {//open bracket
                        if (i<l1 && j<l2 && s1.charAt(i)=='('&&s2.charAt(j)=='('){
                            if (memo[i+1][j+1][k+1][0] > memo[i][j][k][0]+1){
                                memo[i+1][j+1][k+1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else if (i<l1 && s1.charAt(i)=='('){
                            if (memo[i+1][j][k+1][0] > memo[i][j][k][0]+1){
                                memo[i+1][j][k+1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else if (j<l2 && s2.charAt(j)=='('){
                            if (memo[i][j+1][k+1][0] > memo[i][j][k][0]+1){
                                memo[i][j+1][k+1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else {
                            if (memo[i][j][k+1][0] > memo[i][j][k][0]+1){
                                memo[i][j][k+1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                            }
                        }
                    }
                    if (k>0) {//close bracket
                        if (i<l1 && j<l2 && s1.charAt(i)==')'&&s2.charAt(j)==')'){
                            if (memo[i+1][j+1][k-1][0] > memo[i][j][k][0]+1){
                                memo[i+1][j+1][k-1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else if (i<l1 && s1.charAt(i)==')'){
                            if (memo[i+1][j][k-1][0] > memo[i][j][k][0]+1){
                                memo[i+1][j][k-1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else if (j<l2 && s2.charAt(j)==')'){
                            if (memo[i][j+1][k-1][0] > memo[i][j][k][0]+1){
                                memo[i][j+1][k-1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                                //setparent
                            }
                        } else {
                            if (memo[i][j][k-1][0] > memo[i][j][k][0]+1){
                                memo[i][j][k-1] = new int[] {memo[i][j][k][0]+1,i,j,k};
                            }
                        }
                    }
                }
            }
        }

        int bestK = 0;
        int bestVal = INF;
        for (int k = 0; k < 203; k++) {
            if (memo[l1][l2][k][0]+k < bestVal){
                bestVal = memo[l1][l2][k][0]+k;
                bestK = k;
            }
        }
        LinkedList<Character> sol = new LinkedList<>();
        for (int i = 0; i < bestK; i++) sol.add(')');
        int i = l1;
        int j = l2;
        int k = bestK;
        while (i != 0 || j != 0 || k != 0){
            int prevI = memo[i][j][k][1];
            int prevJ = memo[i][j][k][2];
            int prevK = memo[i][j][k][3];
            if (prevK < k)sol.addFirst('(');
            else sol.addFirst(')');
            i = prevI; j = prevJ; k = prevK;
        }

        pw.println(sol.stream().collect(Collector.of(StringBuilder::new,
                StringBuilder::append,
                StringBuilder::append,
                StringBuilder::toString)));

        pw.flush();
    }


    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}