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;
int dp[3005][3005];
int main(){
 string s,w;
 cin>>s>>w;
 reverse(s.begin(),s.end());
 reverse(w.begin(),w.end());
 int ls=s.length();
 int lw=w.length();
 for(int i=1;i<=ls;i++){
   for(int j=1;j<=lw;j++){
       if(s[i-1]==w[j-1])
       dp[i][j]=dp[i-1][j-1]+1;
       else
       dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
   }
}
int len=dp[ls][lw];
for(int i=lw;i>=1;i--){
	for(int j=ls;j>=1;j--)
	if(s[j-1]==w[i-1]&&dp[j][i]==len){
		cout<<s[j-1];
		len--;
		break;
	}
}
cout<<endl;
return 0;
}