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 inf=3005;
string a,b,ans;
int dp[inf][inf];
int sa(char x,char y){
	if(x==y) return 1;
	return 0;
}
void dfs(int x,int y){
	if(!x||!y) return;
	if(a[x]==b[y]){
		ans+=a[x];
		dfs(x-1,y-1);
	}
	else if(dp[x-1][y]>dp[x][y-1]) dfs(x-1,y);
	else dfs(x,y-1);
}
int main(){
	cin>>a>>b;
	a=' '+a;
	b=' '+b;
	for(int i=1;i<a.size();i++){
		for(int j=1;j<b.size();j++){
			dp[i][j]=max(dp[i-1][j-1]+sa(a[i],b[j]),max(dp[i-1][j],dp[i][j-1]));
		}
	}
	dfs(a.size()-1,b.size()-1);
	for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];
	cout<<endl;
	return 0;
}