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 dp[3001][3001];

int main(){
	string S,T; cin>>S>>T;
	int N = S.size(), M = T.size();
	S = "*" + S; T = "*" + T;

	for(int s=1; s<=N; s++)
		for(int t=1; t<=M; t++)
			dp[s][t] = max(max(dp[s][t-1], dp[s-1][t]), dp[s-1][t-1] + (S[s]==T[t]));

	string ans;
	while(N>0 && M>0){
		if(dp[N][M]==dp[N-1][M]) N--;
		else if(dp[N][M]==dp[N][M-1]) M--;
		else{
			ans = S[N] + ans;
			N--; M--;
		}
	}
	cout<< ans <<endl;
}