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<cstdio>
#include<cstring>
int n,m,f[3005][3005],top,lst[3005][3005];
char ans[3005],s[3005],t[3005];
int main()
{
	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++)
	 {
	 	if(f[i-1][j]>f[i][j-1])f[i][j]=f[i-1][j],lst[i][j]=0;
	 	else f[i][j]=f[i][j-1],lst[i][j]=1;
	 	if(s[i]==t[j]&&f[i-1][j-1]+1>f[i][j])
	 	 f[i][j]=f[i-1][j-1]+1,lst[i][j]=2;
	 }
	for(int i=n,j=m;i&&j;)
	 if(!lst[i][j])i--;else
	 if(lst[i][j]==1)j--;else
	 ans[++top]=s[i],i--,j--;
	while(top)printf("%c",ans[top--]);
}