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 {

public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		String s1=sc.next();
		String s2=sc.next();
		int dp[][]=new int[s1.length()+1][s2.length()+1];
		for(int i=1;i<=s1.length();i++)
		{
			for(int j=1;j<=s2.length();j++)
			{
				if(s1.charAt(i-1)==s2.charAt(j-1))
				{
					dp[i][j]=dp[i-1][j-1]+1;
				}else {
					dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
	
		//finding the string
		String ans="";
		int n=s1.length();
		int m=s2.length();
		int i=n;
		int j=m;
		while(i>0&&j>0)
		{
			if(s1.charAt(i-1)==s2.charAt(j-1))
			{
				ans+=s1.charAt(i-1);
				i--;
				j--;
			}else {
				if(dp[i-1][j]>dp[i][j-1])
				{
					i--;
					
				}else {
					j--;
				}
			}
		}
		char reverse[]=ans.toCharArray();
		for( i=reverse.length-1;i>=0;i--)
		{
			System.out.print(reverse[i]);
		}
	}
}