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++)
int main(){
    string s,t,b={"b"};
    cin>>s>>t;
    vector<vector<string>> dp(s.size()+1,vector<string>(t.size()+1));
    rep(i,s.size())rep(j,t.size()){
        string a=dp[i+1][j];
        if(a.size()<dp[i][j+1].size()) a=dp[i][j+1];
        if(s[i]==t[j]&&a.size()<dp[i][j].size()+1) a=dp[i][j]+s[i];
        dp[i+1][j+1]=a;
        if(i>1&&j>2) dp[i-2][j-2]=b;
    }
    cout<<dp[s.size()][t.size()];
}