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 a,b,ans;
int mem[3005][3005];

int go(int x,int y)
{
	if(x>=a.size()||y>=b.size()) return 0;
	if(mem[x][y]!=-1) return mem[x][y];
	if(a[x]==b[y]) return mem[x][y]=go(x+1,y+1)+1;
	return mem[x][y]=max(go(x+1,y),go(x,y+1));
}

void build(int x,int y)
{
	if(x>=a.size()||y>=b.size()) return;
	if(a[x]==b[y]){ans+=a[x]; build(x+1,y+1); return;}
	if(mem[x][y]==go(x+1,y))
	{
		build(x+1,y); return;
	}
	build(x,y+1);
}

int main()
{
	cin >> a >> b;
	memset(mem,-1,sizeof mem);
	go(0,0);
	build(0,0);
	cout << ans << endl;
}