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 a, b;
	cin >> a >> b;
	
	int n = a.length();
	int m = b.length();
	
	vector< vector<int> > dp(n+1, vector<int> (m+1, 0));
	int i, j;
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			if (a[i-1]==b[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	i=n;
	j=m;
	string lcs = "";
	while(i>0 && j>0) {
		if (a[i-1]==b[j-1]) {
			lcs+=a[i-1];
			i--;
			j--;
		}
		else if (dp[i-1][j]>dp[i][j-1])
			i--;
		else
			j--;
	}
	reverse(lcs.begin(), lcs.end());
	cout << lcs << endl;
}