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;
	cin >> S >> T;
	vector<vector<string>> dp_str(2, vector<string>(T.size()+1));
	
	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j < T.size(); j++) {
			if (S[i] == T[j]) {
				dp_str[(i+1)%2][j+1] = dp_str[i%2][j] + S[i];
			}
			else if (dp_str[(i+1)%2][j].size() >= dp_str[i%2][j+1].size()) {
				dp_str[(i+1)%2][j+1] = dp_str[(i+1)%2][j];
			}
			else {
				dp_str[(i+1)%2][j+1] = dp_str[i%2][j+1];
			}
		}
	}
	
	cout << dp_str[S.size()%2][T.size()] << endl;
}