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>
#define rep(i, n) for (int i=0; i<(n); i++)
#define ll long long
using namespace std;

int main() {
  string S,T; cin>>S>>T;
  int s=S.size();
  int t=T.size();
  vector<vector<int>> dp(s+1, vector<int>(t+1, 0));
  rep(i, s) {
    rep(j, t) {
      dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]);
      if (S[i]==T[j]) dp[i+1][j+1]=max(dp[i+1][j+1], dp[i][j]+1);
    }
  }
  
  string res="";
  for (int i=s, j=t; (i>0)&&(j>0);) {
    if (dp[i][j]==dp[i-1][j]) i--;
    else if (dp[i][j]==dp[i][j-1]) j--;
    else {
      res=S[i-1]+res;
      i--; j--;
    }
  }
  cout<<res<<endl;
}