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.*;
import java.io.*;

public class Main {


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

	private void solve() {
		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();
		String L = sc.nextLine();

		int N = S.length();
		int M = L.length();

		long [][] dp =  new long[N+1][M+1];


		for(int i=N-1;i>=0;i--){
			for(int j=M-1;j>=0;j--) {
				char a = S.charAt(i);
				char b = L.charAt(j);

				if (a==b) dp[i][j] = 1+ dp[i+1][j+1];
				else {
					dp[i][j] = Math.max(dp[i+1][j], dp[i][j+1]);
				}
			}
		}

		int i=0,j=0;
		while(i<N && j<M) {
			char a = S.charAt(i);
			char b = L.charAt(j);
			if (a==b) {
				System.out.printf("%c", S.charAt(i));
				i++;
				j++;
			} else {
				if (dp[i+1][j]>=dp[i][j+1]) i++;
				else j++;
			}
		}
	}
}