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;
#define ll long long
#define inf 0x3f3f3f3f
const int N=3e3+10;
char s[N],t[N];
int dp[N][N];
int main()
{
	int len1,len2,l,r,i,j;
	scanf("%s",s+1);
	scanf("%s",t+1);
	len1=strlen(s+1);len2=strlen(t+1);
	for(i=len1;i>=1;i--)
	{
		for(j=len2;j>=1;j--)
		{
			if(s[i]==t[j]) dp[i][j]=dp[i+1][j+1]+1;
			else dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
		}
	}
	l=1;r=1;
	while(l<=len1&&r<=len2)
	{
		if(s[l]==t[r])
		{
			printf("%c",s[l]);
			l++;r++; 
		}
		else if(dp[l][r]==dp[l+1][r]) l++;
		else r++;
	}
	printf("\n");
	return 0;
}