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 <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int main() {
	string s, t; cin >> s >> t;
	vector<string>before(t.size() + 1);
	for (int i = 1; i <= s.size(); i++) {
		vector<string>after(t.size() + 1);
		for (int j = 1; j <= t.size(); j++) {
			if (s[i - 1] == t[j - 1]) {
				string a = before[j - 1] + s[i - 1]; 
				after[j] = a;
			}
			else {
				if (before[j].size() > after[j - 1].size())after[j] = before[j];
				else after[j] = after[j - 1];
			}
		}
		before = after;
	}
	cout << before[t.size()] << endl;
	return 0;
}