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 ll int
const ll N = 3e3 + 5;
string s, t, dp[2][N];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> t;
    for (ll i = 0; i < s.size(); i++)
        for (ll j = 0; j < t.size(); j++)
            if (s[i] == t[j])
                dp[i % 2][j + 1] = dp[!(i % 2)][j], dp[i % 2][j + 1].push_back(s[i]);
            else if (dp[i % 2][j].size() > dp[!(i % 2)][j + 1].size())
                dp[i % 2][j + 1] = dp[i % 2][j];
            else
                dp[i % 2][j + 1] = dp[!(i % 2)][j + 1];
    cout << dp[!(s.size() % 2)][t.size()];
}