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 Lint=long long;

int main()
{
   string s,t; cin>>s>>t;
   int N=s.size(),M=t.size();
   s=' '+s;
   t=' '+t;
   vector<vector<int>> dp(N+1,vector<int>(M+1));
   for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
      if(s[i]==t[j]){ dp[i][j]=dp[i-1][j-1]+1; }
      else{ dp[i][j]=max(dp[i-1][j],dp[i][j-1]); }
   }
   string ans;
   int i=N,j=M;
   while(dp[i][j]>0){
      if(s[i]==t[j]){
         ans=s[i]+ans;
         i--; j--;
      }else{
         if(dp[i-1][j]>=dp[i][j-1]) i--;
         else j--;
      }
   }
   cout<<ans<<endl;
   return 0;
}