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;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=3005;
int dp[N][N],go[N][N];
char s[N],t[N];
int main()
{
int n,m;
scanf("%s %s",s+1,t+1);
n=strlen(s+1);
m=strlen(t+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
if(s[i]==t[j])
{
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
if(dp[i][j]==dp[i-1][j-1]+1)
go[i][j]=1;
}
}
string ans;
int i=n,j=m;
while(i>0 && j>0)
{
if(go[i][j])
{
ans+=s[i];
i--;
j--;
}
else
{
if(dp[i][j-1]==dp[i][j]) j--;
else i--;
}
}
reverse(ans.begin(),ans.end());
cout<<ans;
return 0;
}