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, t;
  cin >> s >> t;
  int ns = s.size(), nt = t.size();
  vector<vector<int>> dp(ns+1, vector<int>(nt+1,0));
  for(int i=0; i<ns; ++i) for(int j=0; j<nt; ++j){
    if(s[i] == t[j]) dp[i+1][j+1] = dp[i][j] +1;
    else{
      dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
    }
  }
  string ans;
  int x = ns, y=nt;
  while(dp[x][y] > 0){
    while(dp[x][y] == dp[x-1][y]) --x;
    while(dp[x][y] == dp[x][y-1]) --y;
    ans = s[x-1] + ans;
    --x; --y;
  }
  cout << ans << endl;
}