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 CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
int main()
{
 string s,t;
 cin>>s>>t;
 string ans="";
 int sl=s.length();
 int tl=t.length();
 int dp[sl+1][tl+1];
 memset(dp,0,sizeof(dp));
 int i,j;
 for(i=1;i<=sl;i++)
 {
 	for(j=1;j<=tl;j++)
 	{
 	 if(s[i-1]==t[j-1])
 	 {
 	    dp[i][j]=dp[i-1][j-1]+1;
	  }
	  else
	  dp[i][j]=max(dp[i-1][j],dp[i][j-1]);	
	  //cout<<dp[i][j]<<" ";
	}
	//cout<<endl;
 }
 i=sl;
 j=tl;
 while(i>0 && j>0)
 {
 	if(s[i-1]==t[j-1])
 	{
 		ans=s[i-1]+ans;
 		i--;
 		j--;
	}
	else
	{
		if(dp[i][j]==dp[i-1][j])
		i--;
		else
		j--;
	}
 }
 cout<<ans<<endl;
 return 0;
}