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>
#define Int int64_t

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;

	int n = s.size(), m = t.size();
	vector<string> dp(m + 1, "");
	for (int i = 0; i < n; ++i) {
		vector<string> nxt(m + 1, "");
		for (int j = 0; j < m; ++j) {
			if (s[i] == t[j]) {
				nxt[j + 1] = dp[j];
				nxt[j + 1].push_back(s[i]);
			} else {
				if (dp[j + 1].size() > nxt[j].size()) {
					nxt[j + 1] = dp[j + 1];
				} else {
					nxt[j + 1] = nxt[j];
				}
			}
		}
		dp = nxt;
	}
	cout << dp[m] << endl;

	return 0;
}