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;

int main(){
 string a,b;
 cin>>a>>b;
 vector<vector<ll>> dp(a.length()+1,vector<ll>(b.length()+1));
 for(ll i=1;i<=a.length();i++){
 	for(ll j=1;j<=b.length();j++){
 		if(a[i-1]==b[j-1]){
 			dp[i][j]=1+dp[i-1][j-1];	
		}	
		else{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
 }
 string sol;
 ll I=a.length(),J=b.length();
 while(dp[I][J]){
 	if(a[I-1]==b[J-1]){
 		string chr="";
 		chr.push_back(a[I-1]);
 		sol=chr+sol;
 		I--,J--;
	}
	else{
		if(dp[I-1][J]==dp[I][J]){
			I--;
		}
		else{
			J--;
		}
	}
 }
 cout<<sol<<endl;
 return 0;
}