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.Arrays;
import java.util.Scanner;

public class Main {

	private static Scanner in;
	private static String s, t;
	private static long[][] dp;
	private static int n, m;
	
	public static void main(String[] args) {
		in = new Scanner(System.in);
		s = in.next();
		t = in.next();
		n = s.length();
		m = t.length();
		dp = new long[n+1][m+1];
		
		for(int i=0; i<dp.length; i++) {
			Arrays.fill(dp[i], -1);
		}
//		System.out.println(solve(0, 0));
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				solve(i, j);
			}
		}
		
		int i = 0;
		int j = 0;
		
		while(i!=n && j!=m) {
			if (s.charAt(i)==t.charAt(j)) {
				System.out.print(s.charAt(i));
				i++;
				j++;
			} else {
				if (dp[i][j]==dp[i][j+1]) {
					j++;
				} else {
					i++;
				}
			}
		}

	}
	
	private static long solve(int i, int j) {
		if (i==n || j==m) return 0;
		
		if (dp[i][j]!=-1) return dp[i][j];
		
		if (s.charAt(i)==t.charAt(j)) {
			return dp[i][j]=1+solve(i+1, j+1);
		} else {
			return dp[i][j] = Math.max(solve(i+1, j), solve(i, j+1));
		}
	}

}