Problem: You are given strings s and t. Find one longest string that is a subsequence of both s and t.

Constraints

* s and t are strings consisting of lowercase English letters.
* 1 \leq |s|, |t| \leq 3000

Input

Input is given from Standard Input in the following format:


s
t


Output

Print one longest string that is a subsequence of both s and t. If there are multiple such strings, any of them will be accepted.

Examples

Input

axyb
abyxb


Output

axb


Input

aa
xayaz


Output

aa


Input

a
z


Output




Input

abracadabra
avadakedavra


Output

aaadara

Solution (in JAVA):

Solution:
import java.nio.charset.IllegalCharsetNameException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        String s = in.next();
        String t = in.next();

        int n = s.length();
        int m = t.length();

        int[][] dp = new int[n + 1][m + 1];



        for (int i = 0; i <= n; i++) {

            for (int j = 0; j <= m; j++) {


                if (i == 0 || j == 0) dp[i][j] = 0;

                else if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    //System.out.println(s.charAt(i-1)+" "+t.charAt(j-1)+" "+i+" "+j);
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {

                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);

                }


            }


        }


//        for (int i = 0; i <= n; i++) {
//            for (int j = 0; j <= m; j++) {
//                System.out.print(dp[i][j] + " ");
//            }
//
//            System.out.println();
//
//        }

        StringBuffer lcs = new StringBuffer("");
        int i=n, j = m;
        while(i>0 && j>0) {
            if(s.charAt(i-1) == t.charAt(j-1)) {
                i--;j--;
                lcs.append(s.charAt(i));
            }
            else if(dp[i-1][j] > dp[i][j-1]) i-- ;
            else j--;
        }
        System.out.println(lcs.reverse().toString());
    }
}