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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str1 = br.readLine();
    String str2 = br.readLine();
    int[][] lcs = new int[str1.length()+1][str2.length()+1];
    int max = 0;
    StringBuilder res = new StringBuilder();
    for(int i=0;i<=str1.length();i++){
      for(int j=0;j<=str2.length();j++){
        if(i==0 || j==0)
          lcs[i][j] = 0;
        else if(str1.charAt(i-1) == str2.charAt(j-1)){
          lcs[i][j] = lcs[i-1][j-1]+1;
          //res += str1.charAt(i-1);
        }
        else
          lcs[i][j] = Math.max(lcs[i-1][j],lcs[i][j-1]);
        max = Math.max(max,lcs[i][j]);
      }
    }
    
    int i=str1.length(),j=str2.length();
    while(i>0 && j>0){
      char a = str1.charAt(i-1);
      char b = str2.charAt(j-1);
      if(a==b){
        res.append(a);
        i--;
        j--;
      }
      else{
        if(lcs[i][j] == lcs[i-1][j]) i--;
        else j--;
      }
    }
   System.out.println(res.reverse().toString());
  }
}