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>
#include<cstring>
#include<algorithm>
using namespace std;
string s,t;
int dp[3001][3001];
int main(){
  cin >> s >> t;
  memset(dp,0,sizeof(dp));
  for(int i=0;i<s.size();i++){
    for(int j=0;j<t.size();j++){
      if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
      else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
    }
  }
  int a=s.size(),b=t.size();
  string res="";
  while(a>0&&b>0){
    if(dp[a-1][b]==dp[a][b]) a--;
    else if(dp[a][b-1]==dp[a][b]) b--;
    else {
      a--;b--;
      res=s[a]+res;
    }
  }
  cout << res << "\n";
  return 0;
}