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 MAXN=3000+30;
char S[MAXN],T[MAXN];
int D[MAXN][MAXN];
int main() {
	scanf("%s %s",S+1,T+1);
	int n=0,m=0;
	while(S[n+1])n++;
	while(T[m+1])m++;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if (S[i]==T[j]) D[i][j]=D[i-1][j-1]+1;
			else D[i][j]=max(D[i-1][j],D[i][j-1]);
		}
	int i=n,j=m;
	string r;
	while (i && j) {
		if (S[i]==T[j]) {
			r+=S[i];
			--i;
			--j;
		} else if(D[i-1][j]<D[i][j-1]) --j;
		else --i;
	}
	reverse(r.begin(),r.end());
	puts(r.c_str());
	return 0;
}