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;

const int N = 3100;
int dp[N][N];

int main(){
	string s, t; cin >> s >> t;
	int lens = s.length(), lent = t.length();
	
	for(int i = 1; i <= lens; i++) for(int j = 1; j <= lent; j++){
		if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
		else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
	}
	
	string res = "";
	int i = lens, j = lent;
	while(i > 0 && j > 0){
		if(dp[i][j] == dp[i-1][j]) i--;
		else if(dp[i][j] == dp[i][j-1]) j--;
		else{
			res += s[i-1];
			i--; j--;
		}
	}
	reverse(res.begin(), res.end());
	cout << res;
	return 0;
}