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.util.*;

public class Main {
    private static String solve(String s, String t) {
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        int[][] lcsLen =  new int[sa.length+1][ta.length+1];

        for (int i = 0; i < sa.length; i++)
            for (int j = 0; j < ta.length; j++) {
                if (sa[i] == ta[j]) lcsLen[i+1][j+1] = 1 + lcsLen[i][j];
                else lcsLen[i+1][j+1] = Math.max(lcsLen[i+1][j], lcsLen[i][j+1]);
            }

        int maxLen = lcsLen[sa.length][ta.length];
        if (maxLen == 0) return "";
        char[] lcs = new char[maxLen];

        int i = sa.length;
        int j = ta.length;
        int k = maxLen-1;
        while (k >= 0) {
            if (j > 0 && lcsLen[i][j] == lcsLen[i][j-1]) j--;
            else if (i > 0 && lcsLen[i][j] == lcsLen[i-1][j]) i--;
            else {
                lcs[k--] = sa[i-1];
                i--;
                j--;
            }
        }

        return new String(lcs);
    }

    public static void main(String[] args) {
        String s, t;
        try (Scanner scanner = new Scanner(System.in)) {
            s = scanner.nextLine();
            t = scanner.nextLine();
        }

        String result = solve(s, t);
        System.out.println(result);
    }
}