You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a subsequence of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Subsequence of string s is any such string that can be obtained by erasing zero or more characters (not necessarily consecutive) from string s.

Input

The first line contains string a, and the second line — string b. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters.

Output

On the first line output a subsequence of string a, obtained from b by erasing the minimum number of consecutive characters.

If the answer consists of zero characters, output «-» (a minus sign).

Examples

Input

hi
bob


Output

-


Input

abca
accepted


Output

ac


Input

abacaba
abcdcba


Output

abcba

Note

In the first example strings a and b don't share any symbols, so the longest string that you can get is empty.

In the second example ac is a subsequence of a, and at the same time you can obtain it by erasing consecutive symbols cepted from string b.
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC)throws Exception{
        String a = n(), b = n();
        int A = 26;
        int n = a.length(), m = b.length();
        int[][] prev = new int[2+n][A], nxt = new int[2+n][A];
        for(int i = 0; i< A; i++)prev[0][i] = nxt[n+1][i] = -1;
        
        for(int i = 1; i<= n+1; i++){
            for(int j = 0; j< A; j++)prev[i][j] = prev[i-1][j];
            if(i<=n)prev[i][a.charAt(i-1)-'a'] = i;
        }
        
        for(int i = n; i>= 0; i--){
            for(int j = 0; j< A; j++)nxt[i][j] = nxt[i+1][j];
            if(i>= 1)nxt[i][a.charAt(i-1)-'a'] = i;
        }
        int[] prePos = new int[2+m], sufPos = new int[2+m];
        Arrays.fill(prePos, -1);
        Arrays.fill(sufPos, -1);
        prePos[0] = 0;sufPos[m+1] = n+1;
        for(int i = 1; i<= m; i++){
            if(prePos[i-1] == -1 || nxt[prePos[i-1]+1][b.charAt(i-1)-'a'] == -1)prePos[i] = -1;
            else prePos[i] = nxt[prePos[i-1]+1][b.charAt(i-1)-'a'];
        }
        
        sufPos[m+1] = n+1;
        for(int i = m; i>= 1; i--){
            if(sufPos[i+1] == -1 || prev[sufPos[i+1]-1][b.charAt(i-1)-'a'] == -1)sufPos[i] = -1;
            else sufPos[i] = prev[sufPos[i+1]-1][b.charAt(i-1)-'a'];
        }
        
        int ptr = m+1;
        while(sufPos[ptr-1] != -1)ptr--;
        int l = 0, r = ptr;int sz = r-l-1;
        
        for(int i = 1; i<= m; i++){
            if(prePos[i] == -1)break;
            ptr = Math.max(ptr, i+1);
            while(ptr <= m && sufPos[ptr] <= prePos[i])ptr++;
            
            if(ptr-i-1 < sz){
                sz = ptr-i-1;
                l = i;
                r = ptr;
            }
        }
        String ans = b.substring(0, l)+b.substring(r-1);
        if(ans.length() == 0)pn("-");
        else pn(ans);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e18, mod = (long)998244353;
    final int INF = (int)1e9, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.00000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-6;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("input.txt");
            out = new PrintWriter("output.txt");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}
 
    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }
 
        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}