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 <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
 
char S[3030],T[3030]; int D[3030][3030];
 
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;
}