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 rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
string dp[2][3001];
int main(){
    string s,t;
    cin>>s>>t;
    rep(i,s.size())rep(j,t.size()){
        dp[(i+1)%2][j+1]=dp[(i+1)%2][j];
        if(dp[(i+1)%2][j+1].size()<dp[i%2][j+1].size()) dp[(i+1)%2][j+1]=dp[i%2][j+1];
        if(s[i]==t[j]&&dp[(i+1)%2][j+1].size()<dp[i%2][j].size()+1) dp[(i+1)%2][j+1]=dp[i%2][j]+s[i];
    }
    cout<<dp[s.size()%2][t.size()]<<"\n";
}