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;
string s,t;
int dp[3010][3010];
int fr[3010][3010];
void ct(int x,int y){
	switch(fr[x][y]){
		case 0:
			return;
		case 1:
			ct(x-1,y-1);
			cout<<s[x-1];
			break;
		case 2:
			ct(x,y-1);
			break;
		case 3:
			ct(x-1,y);
			break;
	}
}
int main()
{
	cin>>s>>t;
	for(int i=0;i<s.size();i++)
		for(int j=0;j<t.size();j++){
			if(s[i]==t[j])
				fr[i+1][j+1]=1,dp[i+1][j+1]=dp[i][j]+1;
			else{
				if(dp[i][j+1]<=dp[i+1][j])
					dp[i+1][j+1]=dp[i+1][j],fr[i+1][j+1]=2;
				else dp[i+1][j+1]=dp[i][j+1],fr[i+1][j+1]=3;
			}
		}
	ct(s.size(),t.size());
	return 0;
}