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;

pair<int, char> d[3333][3333];
int main() {
	string s, t, u;
	cin >> s >> t;
	for (int i = s.length(); i--;) {
		for (int j = t.length(); j--;) {
			if (s[i] == t[j]) d[i][j] = { d[i + 1][j + 1].first + 1,s[i] };
			else d[i][j] = max(d[i + 1][j], d[i][j + 1]);
		}
	}
	for (int i = 0, j = 0; d[i][j].first;) {
		if (s[i] == t[j]) u += d[i++][j++].second;
		else d[i + 1][j] > d[i][j + 1] ? i++ : j++;
	}
	cout << u << endl;
	return 0;
}