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:
/*package whatever //do not write package name here */

import java.util.*;
import java.lang.*;
import java.lang.reflect.Array;
import java.io.*;

class Main {
    static int dp[][];
    
	public static void main (String[] args)throws IOException{
		//code
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		String s=br.readLine();
		String t=br.readLine();
           int n=s.length(),m=t.length();


        dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s.charAt(i-1)==t.charAt(j-1))dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        StringBuilder res=new StringBuilder();
        int i=n,j=m;
        while(i>0&&j>0){
           if(dp[i][j]>dp[i-1][j]&&dp[i][j]>dp[i][j-1]){
               res.append(s.charAt(i-1));
               i--;j--;
           }
           else{
               if(dp[i-1][j]>dp[i][j-1])i--;
               else j--;
           }

        }
        
           // for( i=1;i<=n;i++)
             //System.out.println(Arrays.toString(dp[i]));
            System.out.print(res.reverse());
		
		    
	
		
	}
}