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<iostream>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	int s1=s.size(),t1=t.size();
	string dp[2][t1+1];
	for(int i=0;i<=t1;++i)
		dp[0][i]="";
	for(int i=1;i<=s1;++i)
	{
		dp[1][0]="";
		dp[0][0]="";
		for(int j=1;j<=t1;++j)
		{
			if(s[i-1]==t[j-1])
			{
				dp[1][j]=dp[0][j-1];
				dp[1][j]+=s[i-1];
			}
			else
			{
				if(dp[0][j].size()>dp[1][j-1].size())
					dp[1][j]=dp[0][j];
				else
					dp[1][j]=dp[1][j-1];
			}
		}

		for(int k=0;k<=t1;++k)
			dp[0][k]=dp[1][k];
	}
	cout<<dp[1][t1];
}