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;
long long mod=1e9+7;

int main() 
{ 
  string s,t;
  cin>>s>>t;
  int m=s.size();
  int n=t.size(); 
  int arr[m+1][n+1]; 
  for (int i=0;i<=m; i++){ 
	for (int j=0;j<=n;j++){ 
	   if(i==0||j==0) arr[i][j]=0; 
	   else if(s[i-1]==t[j-1]) arr[i][j]=arr[i-1][j-1] + 1; 
	   else arr[i][j]=max(arr[i-1][j],arr[i][j-1]); 
	 } 
   } 
  string res="";

  for(int i=m,j=n;i>=1,j>=1;){ 
	
	  if(s[i-1]==t[j-1]){res+=s[i-1];i--;j--;} 
 	  else if(arr[i-1][j]>arr[i][j-1]) i--;
	  else j--;
   } 
   reverse(res.begin(),res.end());
   cout<<res;
return 0; 
}