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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author lebegio
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyReader in = new MyReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        TreeSet<Integer>[] poz = new TreeSet['z' - 'a' + 1];
        int fromOk = 0;
        int toOk = 1000000;

        public void solve(int testNumber, MyReader in, PrintWriter out) {
            String strA = in.next();
            String strB = in.next();
            for (int i = 0; i < poz.length; i++) poz[i] = new TreeSet<>();

            char[] a = strA.toCharArray();
            char[] b = strB.toCharArray();
            int p = 0;
            for (char x : a) {
                poz[x - 'a'].add(p++);
            }

            RedBlackBST<Integer, Integer> checkedL = new RedBlackBST<>();
            RedBlackBST<Integer, Integer> checkedR = new RedBlackBST<>();
            Integer P = -1;
            int pL = 0;
            for (int i = 0; i < b.length && P != null; i++) {
                P = poz[b[i] - 'a'].higher(P);
                if (P != null) {
                    pL++;
                    checkedL.put(P, i);
                }
            }

            P = a.length;
            int pR = 0;
            for (int i = b.length - 1; i >= 0 && P != null; i--) {
                P = poz[b[i] - 'a'].lower(P);
                if (P != null) {
                    pR++;
                    checkedR.put(P, i);
                }
            }
            if (pR == 0 && pL == 0) {
                out.println("-");
                return;
            } else if (pR == b.length) {
                out.println(b);
                return;
            } else if (pR == 0) {
                int t = checkedL.max();
                int k = checkedL.get(t);
                out.println(strB.substring(0, k + 1));
                return;
            } else if (pL == 0) {
                int t = checkedR.min();
                int k = checkedR.get(t);
                out.println(strB.substring(k));
                return;
            }


            while (!checkedR.isEmpty()) {
                int t = checkedR.max();
                int k = checkedR.get(t);
                if (toOk - fromOk > k - 1) {
                    fromOk = 0;
                    toOk = k - 1;
                }
                checkedR.deleteMax();

                Integer t1 = checkedL.floor(t - 1);
                if (t1 == null) continue;
                Integer k1 = checkedL.get(t1);

                if (k1 + 1 <= k - 1 && k - k1 - 2 < toOk - fromOk) {
                    fromOk = k1 + 1;
                    toOk = k - 1;
                }

            }

            while (!checkedL.isEmpty()) {
                int t = checkedL.max();
                int k = checkedL.get(t);
                if (toOk - fromOk > b.length - k - 2) {
                    fromOk = k + 1;
                    toOk = b.length - 1;
                }
                checkedL.deleteMax();
            }

            out.println(strB.substring(0, fromOk) + strB.substring(toOk + 1));
        }

    }

    static class RedBlackBST<Key extends Comparable<Key>, Value> {
        private static final boolean RED = true;
        private static final boolean BLACK = false;
        private Node root;

        public RedBlackBST() {
        }

        private boolean isRed(Node x) {
            if (x == null) return false;
            return x.color == RED;
        }

        private int size(Node x) {
            if (x == null) return 0;
            return x.size;
        }

        public boolean isEmpty() {
            return root == null;
        }

        public Value get(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to get() is null");
            return get(root, key);
        }

        private Value get(Node x, Key key) {
            while (x != null) {
                int cmp = key.compareTo(x.key);
                if (cmp < 0) x = x.left;
                else if (cmp > 0) x = x.right;
                else return x.val;
            }
            return null;
        }

        public boolean contains(Key key) {
            return get(key) != null;
        }

        public void put(Key key, Value val) {
            if (key == null) throw new IllegalArgumentException("first argument to put() is null");
            if (val == null) {
                delete(key);
                return;
            }

            root = put(root, key, val);
            root.color = BLACK;
            // assert check();
        }

        private Node put(Node h, Key key, Value val) {
            if (h == null) return new Node(key, val, RED, 1);

            int cmp = key.compareTo(h.key);
            if (cmp < 0) h.left = put(h.left, key, val);
            else if (cmp > 0) h.right = put(h.right, key, val);
            else h.val = val;

            // fix-up any right-leaning links
            if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
            if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
            if (isRed(h.left) && isRed(h.right)) flipColors(h);
            h.size = size(h.left) + size(h.right) + 1;

            return h;
        }

        private Node deleteMin(Node h) {
            if (h.left == null)
                return null;

            if (!isRed(h.left) && !isRed(h.left.left))
                h = moveRedLeft(h);

            h.left = deleteMin(h.left);
            return balance(h);
        }

        public void deleteMax() {
            if (isEmpty()) throw new NoSuchElementException("BST underflow");

            // if both children of root are black, set root to red
            if (!isRed(root.left) && !isRed(root.right))
                root.color = RED;

            root = deleteMax(root);
            if (!isEmpty()) root.color = BLACK;
            // assert check();
        }

        private Node deleteMax(Node h) {
            if (isRed(h.left))
                h = rotateRight(h);

            if (h.right == null)
                return null;

            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);

            h.right = deleteMax(h.right);

            return balance(h);
        }

        public void delete(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to delete() is null");
            if (!contains(key)) return;

            // if both children of root are black, set root to red
            if (!isRed(root.left) && !isRed(root.right))
                root.color = RED;

            root = delete(root, key);
            if (!isEmpty()) root.color = BLACK;
            // assert check();
        }

        private Node delete(Node h, Key key) {
            // assert get(h, key) != null;

            if (key.compareTo(h.key) < 0) {
                if (!isRed(h.left) && !isRed(h.left.left))
                    h = moveRedLeft(h);
                h.left = delete(h.left, key);
            } else {
                if (isRed(h.left))
                    h = rotateRight(h);
                if (key.compareTo(h.key) == 0 && (h.right == null))
                    return null;
                if (!isRed(h.right) && !isRed(h.right.left))
                    h = moveRedRight(h);
                if (key.compareTo(h.key) == 0) {
                    Node x = min(h.right);
                    h.key = x.key;
                    h.val = x.val;
                    // h.val = get(h.right, min(h.right).key);
                    // h.key = min(h.right).key;
                    h.right = deleteMin(h.right);
                } else h.right = delete(h.right, key);
            }
            return balance(h);
        }

        private Node rotateRight(Node h) {
            // assert (h != null) && isRed(h.left);
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = x.right.color;
            x.right.color = RED;
            x.size = h.size;
            h.size = size(h.left) + size(h.right) + 1;
            return x;
        }

        private Node rotateLeft(Node h) {
            // assert (h != null) && isRed(h.right);
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = x.left.color;
            x.left.color = RED;
            x.size = h.size;
            h.size = size(h.left) + size(h.right) + 1;
            return x;
        }

        private void flipColors(Node h) {
            // h must have opposite color of its two children
            // assert (h != null) && (h.left != null) && (h.right != null);
            // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
            //    || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
            h.color = !h.color;
            h.left.color = !h.left.color;
            h.right.color = !h.right.color;
        }

        private Node moveRedLeft(Node h) {
            // assert (h != null);
            // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

            flipColors(h);
            if (isRed(h.right.left)) {
                h.right = rotateRight(h.right);
                h = rotateLeft(h);
                flipColors(h);
            }
            return h;
        }

        private Node moveRedRight(Node h) {
            // assert (h != null);
            // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
            flipColors(h);
            if (isRed(h.left.left)) {
                h = rotateRight(h);
                flipColors(h);
            }
            return h;
        }

        private Node balance(Node h) {
            // assert (h != null);

            if (isRed(h.right)) h = rotateLeft(h);
            if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
            if (isRed(h.left) && isRed(h.right)) flipColors(h);

            h.size = size(h.left) + size(h.right) + 1;
            return h;
        }

        public Key min() {
            if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
            return min(root).key;
        }

        private Node min(Node x) {
            // assert x != null;
            if (x.left == null) return x;
            else return min(x.left);
        }

        public Key max() {
            if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
            return max(root).key;
        }

        private Node max(Node x) {
            // assert x != null;
            if (x.right == null) return x;
            else return max(x.right);
        }

        public Key floor(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to floor() is null");
            if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
            Node x = floor(root, key);
            if (x == null) return null;
            else return x.key;
        }

        private Node floor(Node x, Key key) {
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x;
            if (cmp < 0) return floor(x.left, key);
            Node t = floor(x.right, key);
            if (t != null) return t;
            else return x;
        }

        private class Node {
            private Key key;
            private Value val;
            private Node left;
            private Node right;
            private boolean color;
            private int size;

            public Node(Key key, Value val, boolean color, int size) {
                this.key = key;
                this.val = val;
                this.color = color;
                this.size = size;
            }

        }

    }

    static class MyReader {
        private BufferedReader buffReader;
        private StringTokenizer strTokenizer;
        private static final int SIZE = 32768;

        public MyReader(InputStream inputStream) {
            buffReader = new BufferedReader(new InputStreamReader(inputStream), SIZE);
        }

        public String next() {
            if (strTokenizer == null || !strTokenizer.hasMoreTokens()) {
                try {
                    strTokenizer = new StringTokenizer(buffReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return strTokenizer.nextToken();
        }

    }
}

