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:
//Problem *
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,dp[N][N],e[N][N],t;
char a[N],b[N],s[N];
int main(){
	scanf("%s%s",a+1,b+1);n=strlen(a+1),m=strlen(b+1);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		int x=dp[i][j-1],y=dp[i-1][j],z=dp[i-1][j-1]+1;
		if(x<y)dp[i][j]=y,e[i][j]=1;else dp[i][j]=x;
		if(a[i]==b[j]&&dp[i][j]<z)dp[i][j]=z,e[i][j]=2;
	}
	int x=n,y=m;
	while(x&&y){
		if(e[x][y]==2)s[++t]=a[x],--x,--y;
		else{if(e[x][y])--x;else --y;}
	}
	for(int i=t;i;i--)printf("%c",s[i]);
	return 0;
}