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;
using LL=long long;
int main(){
  string S,T;cin>>S>>T;
  vector<string>dp(S.length(),"");
  for(int i=0;i<T.length();i++){
    vector<string>dp2(S.length());
    for(int j=0;j<S.length();j++){
      if(j==0)
        dp2[j]=dp[j];
      else
        if(dp2[j-1].length()<dp[j].length())
          dp2[j]=dp[j];
        else
          dp2[j]=dp2[j-1];
      
      if(T[i]==S[j] && (j==0 ? 0 : dp[j-1].length())+1>dp2[j].length())
        dp2[j]=(j==0 ? "" : dp[j-1]),
        dp2[j].push_back(T[i]);
    }
    dp=dp2;
  }
  cout<<dp.back()<<endl;
}