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;


const int N=3100;

int	f[N][N];   

char ans[N];int pos;
int main()
{
	char s[N],t[N];
	cin>>s+1>>t+1;
	int n=strlen(s+1);
	int m=strlen(t+1);
	string x="";
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(s[i]==t[j])
			{
				f[i][j]=f[i-1][j-1]+1;
			}
			else{
					f[i][j]=max(f[i-1][j],f[i][j-1]);
				}
		}
	   int len=f[n][m];
    int i=n,j=m;pos=len-1;
    while(f[i][j])
    {
        if(f[i][j]==f[i-1][j]) i--;
        else if(f[i][j]==f[i][j-1]) j--;
        else ans[pos--]=s[i],i--,j--;
	}
	cout<<ans<<endl;
}