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;
#define AC ios::sync_with_stdio(0),cin.tie(0);
#define ll long long int

string s1,s2;
const int N=3005;
int dp[N][N];
int main(){
  	AC
	cin>>s1>>s2;
	for(int i=s1.length();i>=0;--i){
        for(int j =s2.length();j>=0;--j){
            if(s1[i]==s2[j])dp[i][j]=dp[i+1][j+1]+1;
            else dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
        }
    }	
    int i=0,j=0;
    
    while(i<s1.length() && j<s2.length()){
    	if(s1[i]==s2[j]){
            cout<<s1[i];
            i++,j++;
        }
        else if(dp[i][j]==dp[i+1][j]) i++;
        else j++;
	}
	cout<<endl;
}