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:
// F - LCS
#include <bits/stdc++.h>
using namespace std;

int main(){
	string S,T; cin>>S>>T;
	int Ns = S.size(), Nt = T.size();

	vector<vector<int>> dp(Nt+1, vector<int>(Ns+1));
	for(int t=1; t<=Nt; t++)
		for(int s=1; s<=Ns; s++)
			if(T[t-1]==S[s-1]) dp[t][s] = dp[t-1][s-1] + 1;
			else dp[t][s] = max(dp[t][s-1], dp[t-1][s]);

	string ans;
	int t = Nt, s = Ns;
	while(t>=1 && s>=1){
		if(dp[t][s]==dp[t][s-1]) s--;
		else if(dp[t][s]==dp[t-1][s]) t--;
		else{
			t--; s--;
			ans = S[s] + ans;
		}
	}
	cout<< ans <<endl;
}