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;

const int N=3001;
int dp[N][N];
int main()
{
	string s,t;
	cin >> s >> t;
	int n=s.size(),m=t.size();
	for(int i=n-1;i>=0;i--)
        for(int j=m-1;j>=0;j--)
            if(s[i]==t[j])
                dp[i][j]=dp[i+1][j+1]+1;
            else
                dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
    string sol;
    int i=0,j=0;
    while(i<n&&j<m)
        if(s[i]==t[j])
            sol+=s[i],i++,j++;
        else
            if(dp[i+1][j]>dp[i][j+1])
                i++;
            else
                j++;
    cout << sol << endl;
    return 0;
}