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>
#include<string>
using namespace std;
static const int MAX_SIZE=3000;
string dp[2][MAX_SIZE+10];
int main(void){
	string s,t,ans;
		cin >> s >> t;
	int ss=s.size(),ts=t.size();
	
	for(int i=ss-1,k=0;i>=0;i--,k^=1){
		for(int j=ts-1;j>=0;j--){
			if(s[i]==t[j])
				dp[k][j]=dp[k^1][j+1]+s[i];
			else
				dp[k][j]=(dp[k][j+1].size()>dp[k^1][j].size()?dp[k][j+1]:dp[k^1][j]);
		}
	}
	
	for(int i=dp[ss%2^1][0].size()-1;i>=0;i--)
		cout << dp[ss%2^1][0][i];
	cout << endl;
	
	return 0;
}