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>
#define MAXN 3500
using namespace std;

int LCS[MAXN][MAXN];
char L[MAXN];

int main(){
	string s1,s2;
	cin>>s1>>s2;
	int x = s1.size();
	int y = s2.size();
	int i,j;
	for(i=0;i<=x;i++)
		for(j=0;j<=y;j++){
			if(i==0 || j==0)LCS[i][j]=0;
			else if(s1[i-1]==s2[j-1]){
				LCS[i][j]=1+LCS[i-1][j-1];
			}else{
				LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
			}
		}

	int index = LCS[x][y];
	L[index+1]='\0';
	
	while(i>0 && j>0){
		if(s1[i-1]==s2[j-1]){
			L[index]=s1[i-1];
			i--;j--;index--;
		}else{
			if(LCS[i][j-1]>LCS[i-1][j]){
				j--;
			}else i--;
			
		}
		
	}
	cout<<L<<endl;
}