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;
int main(){
string s;
  string t;
  cin>>s>>t;
  int N=s.size();
  int M=t.size();
  vector<vector<int>>dp(N+1,vector<int>(M+1,0));
  for(int i=1;i<=N;i++){
  for(int j=1;j<=M;j++){
   if(s.at(i-1)==t.at(j-1))
     dp[i][j]=1+dp[i-1][j-1];
    else
      dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  }
  }string ans="";
  int I=N; int J=M;
  while(1<=I && 1<=J){
  if(dp[I][J]==dp[I-1][J]){
   I--;
  }else if(dp[I][J]==dp[I][J-1]){
   J--;
  }else{
  ans=s.at(I-1)+ans; I--; J--;
  }
  
  }cout<<ans<<endl;
    return 0;
}