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;
typedef long long ll;
const int N=3500;
char s[N],t[N],ans[N];
ll a[N][N],n,m,i,j,cnt=0;
int main(){
	cin>>s>>t;
	n=strlen(s); m=strlen(t);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(s[i-1]==t[j-1]) a[i][j]=a[i-1][j-1]+1;
			else a[i][j]=max(a[i][j-1],a[i-1][j]);
		}
	}
	i=n;j=m;
	if(a[i][j]==0){
		cout<<" ";
		return 0;
	}
	for(;;){
		if(s[i-1]==t[j-1]){
			ans[cnt++]=t[j-1];
			--i;--j;
		}
		else{
			if(a[i][j]==a[i-1][j]) --i;
			else j--;
		}
		if(i==0||j==0) break;
	}
	for(i=cnt-1;i>=0;i--) cout<<ans[i];
}