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 <iostream>
#include <string>
#include <algorithm>

std::string s, t;

int dp[3001][3001];

int main(){
  std::cin >> s >> t;
  int n = s.length();
  int m = t.length();

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
    }
  }
  std::string ans;

  while(n && m){
    if(s[n-1] == t[m-1]) ans.push_back(s[n-1]), n--, m--;
    else if(dp[n-1][m] > dp[n][m-1]) n--;
    else m--;
  }
  std::reverse(ans.begin(), ans.end());

  std::cout << ans << std::endl;

  return 0;
}