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 a, b;
int dp[3010][3010];
int n, m;
deque<char> ans;

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i] == b[j])
				dp[i + 1][j + 1] = dp[i][j] + 1;
			else 
				dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
		}
	}
	int x = n - 1, y = m - 1;
	while (x >= 0 && y >= 0) {
		if (a[x] == b[y]) ans.push_front(a[x]), x--, y--;
		else if (dp[x][y + 1] > dp[x + 1][y]) x--;
		else y--;
	}
	for(auto ch : ans) printf("%c", ch);
}

int main() {
	cin >> a >> b;
	n = a.size(), m = b.size();
	solve();
	return 0;
}