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 int long long
signed main(){
  string S,T;
  cin>>S>>T;
  int N=S.size(),M=T.size();
  vector<vector<int>> A(N+1,vector<int>(M+1));
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      if(S[i-1]==T[j-1])
        A[i][j]=max({A[i-1][j-1]+1,A[i-1][j],A[i][j-1]});
      else
        A[i][j]=max(A[i-1][j],A[i][j-1]);
    }
  }
  string U="";
  int j=N,k=M;
  for(int i=A[N][M];i>0;i--){
    for(;A[j][k]==i;j--);j++;
    for(;A[j][k]==i;k--);j--;
    U+=S[j];
  }
  reverse(U.begin(),U.end());
  cout<<U<<endl;
}