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;

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef vector<string> vs;
typedef vector<vs> vvs;

void chmaxs(string& s, string& t) {
	if(s.size() < t.size()) s = t;
}
 
int main() {
//	cout << fixed << setprecision(15);
	string s, t;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	vvs dp(2, vs(m+1));
	rep(i, n) rep(j, m) {
		int prev = i % 2, next = 1 - prev;
		chmaxs(dp[next][j+1], dp[prev][j+1]);
		chmaxs(dp[next][j+1], dp[next][j]);
		if(s[i] == t[j]) {
			string u = dp[prev][j] + s[i];
			chmaxs(dp[next][j+1], u);
		}
	}
	cout << dp[n % 2][m] << endl;
}