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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int MAX_N = 3005;

char a[MAX_N],b[MAX_N];
int n,m,dp[MAX_N][MAX_N];

int main()
{
	scanf("%s",a);
	scanf("%s",b);
	n=strlen(a),m=strlen(b);
	for (int i=n-1; i>=0; i--)
		for (int j=m-1; j>=0; j--)
			if (a[i]==b[j])
				dp[i][j]=1+dp[i+1][j+1];
			else
				dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
	int i=0,j=0;
	while (i<n&&j<m)
		if (a[i]==b[j])
		{
			putchar(a[i]);
			i++,j++;
		}
		else if (dp[i][j]==dp[i+1][j])
			i++;
		else
			j++;
	printf("\n");
	return 0;
}