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 {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();

        int[][] dp = new int[s.length+1][t.length+1];

        for (int i=1; i<=s.length; i++) {
            for (int j=1; j<=t.length; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        int i = s.length - 1, j = t.length - 1;

        while (0 <= i && 0 <= j) {
            if (s[i] == t[j]) {
                sb.append(s[i]);
                i--;
                j--;
            } else {
                if (dp[i+1][j] < dp[i][j+1]) {
                    i--;
                } else {
                    j--;
                }
            }
        }

        System.out.println(sb.reverse().toString());

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



    }
}