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 <algorithm>
using namespace std;
int dp[3010][3010]={0};
int main() {
  string s,t,res="";
  cin>>s>>t;
  int ss=s.size(),ts=t.size();
  for(int i=0;i<ss;++i)for(int j=0;j<ts;++j){
    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
    if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;
  }
  while(ss>0&&ts>0)
    if(dp[ss][ts]==dp[ss-1][ts])--ss;
    else if(dp[ss][ts]==dp[ss][ts-1])--ts;
    else{--ss;--ts;res=s[ss]+res;}
  cout<<res<<endl;
}