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;

string s, t, ans;
int dp[3010][3010];

int f(int n, int m) {
	if (n<0 || m<0) return 0;
	if (dp[n][m] != -1) return dp[n][m];
	if (s[n] == t[m]) dp[n][m] = 1 + f(n-1, m-1);
	else dp[n][m] = max(f(n-1, m), f(n, m-1));
	return dp[n][m];
}

void rec(int n, int m) {
	if (n<0 || m<0) return;
	if (s[n] == t[m]) {ans = s[n] + ans; rec(n-1, m-1);}
	else if (f(n-1, m) > f(n, m-1)) rec(n-1, m);
	else rec(n, m-1);
}

int main() {
	cin >> s;
	cin >> t;
	memset(dp,-1, sizeof(dp));
	rec(s.length()-1, t.length()-1);
	cout << ans << endl;
	return 0;
}