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;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

int main(){
	string s,t;
	cin >> s >> t;
	int n(s.size()), m(t.size());
	vector<vector<string>> dp(2, vector<string>(m+10));
	rep(i,n){
		rep(j,m){
			if(s[i] == t[j]){
				dp[1][j+1] = dp[0][j] + s[i];
			}else{
				if(dp[1][j].size() > dp[0][j+1].size()){
					dp[1][j+1] = dp[1][j];
				}else{
					dp[1][j+1] = dp[0][j+1];
				}
			}
		}
		dp[0] = dp[1];
	}
	cout << dp[1][m] << endl;
	return 0;
}