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>
int dp[3005][3005],t[3005][3005];
char s1[3005],s2[3005],s[3005];
int main(){
	scanf("%s%s",s1+1,s2+1);
	int n=strlen(s1+1),m=strlen(s2+1);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			if (s1[i]==s2[j] && dp[i-1][j-1]+1>dp[i][j])
				dp[i][j]=dp[i-1][j-1]+1,t[i][j]=0;
			if (dp[i-1][j]>dp[i][j]) dp[i][j]=dp[i-1][j],t[i][j]=1;
			if (dp[i][j-1]>dp[i][j]) dp[i][j]=dp[i][j-1],t[i][j]=2;
		}
	int ans=dp[n][m];
	if (!ans) return 0;
	int i=n,j=m;
	while (i && j){
		if (!t[i][j]) {
			s[ans--]=s1[i];
			i--,j--;
		}else if (t[i][j]==1) i--;
		else j--;
	}
	printf("%s\n",s+1); 
}