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;

int main() {
	string S, T, ans = "";
	static long long DP[3010][3010] = {}, len;
	cin >> S >> T;
	for (int i = 1; i <= S.size(); i++) {
		for (int j = 1; j <= T.size(); j++) {
			if (S[i - 1] == T[j - 1]) DP[i][j] = DP[i - 1][j - 1] + 1;
			else DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
		}
	}
	int i = S.size(), j = T.size();
	len = DP[i][j];
	while (len > 0) {
		if (S[i - 1] == T[j - 1]) {
			ans = S[i - 1] + ans;
			len--;
			i--;
			j--;
		}
		else if (DP[i][j] == DP[i - 1][j]) i--;
		else j--;
	}
	cout << ans;
}