Problem: In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF.

You are given two strings s1, s2 and another string called virus. Your task is to find the longest common subsequence of s1 and s2, such that it doesn't contain virus as a substring.

Input

The input contains three strings in three separate lines: s1, s2 and virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Each string consists only of uppercase English letters.

Output

Output the longest common subsequence of s1 and s2 without virus as a substring. If there are multiple answers, any of them will be accepted. 

If there is no valid common subsequence, output 0.

Examples

Input

AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ


Output

ORZ


Input

AA
A
A


Output

0

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            BLuckyCommonSubsequence solver = new BLuckyCommonSubsequence();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class BLuckyCommonSubsequence {
        int shift = 1000;
        int[][][] prev;
        int[][][] dp;
        int end;
        Debug debug = new Debug(true);

        public void update(int i, int j, int k, int ni, int nj, int nk, int val) {
            if (nk == end) {
                return;
            }
            if (dp[ni][nj][nk] < val) {
                dp[ni][nj][nk] = val;
                prev[ni][nj][nk] = (i * shift + j) * shift + k;
            }
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] a = in.rs().toCharArray();
            char[] b = in.rs().toCharArray();
            char[] virus = in.rs().toCharArray();
            AhoCorasick ac = new AhoCorasick('A', 'Z', virus.length);
            ac.prepareBuild();
            for (char c : virus) {
                ac.build(c);
            }
            end = ac.buildLast;
            int[] topo = ac.endBuild();
            int[][] next = ac.next;
            int inf = (int) 1e9;
            int n = a.length;
            int m = b.length;

            prev = new int[n + 1][m + 1][topo.length];
            dp = new int[n + 1][m + 1][topo.length];
            SequenceUtils.deepFill(dp, -inf);
            dp[0][0][0] = 0;
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    for (int k = 0; k < topo.length; k++) {
                        //both add
                        if (i < n && j < m && a[i] == b[j]) {
                            update(i, j, k, i + 1, j + 1, next[a[i] - 'A'][k], dp[i][j][k] + 1);
                        }
                        if (j < m) {
                            update(i, j, k, i, j + 1, k, dp[i][j][k]);
                        }
                        if (i < n) {
                            update(i, j, k, i + 1, j, k, dp[i][j][k]);
                        }
                    }
                }
            }

            debug.debug("dp", dp);
            int best = 0;
            for (int i = 0; i < topo.length; i++) {
                if (dp[n][m][i] > dp[n][m][best]) {
                    best = i;
                }
            }
            if (dp[n][m][best] == 0) {
                out.println(0);
                return;
            }

            //start from best
            StringBuilder res = new StringBuilder();
            int x = n;
            int y = m;
            while (x > 0 && y > 0) {
                int transfer = prev[x][y][best];
                int nk = transfer % shift;
                transfer /= shift;
                int ny = transfer % shift;
                transfer /= shift;
                int nx = transfer % shift;
                if (nx < x && ny < y) {
                    res.append(a[x - 1]);
                }
                x = nx;
                y = ny;
                best = nk;
            }

            res.reverse();
            out.println(res.toString());
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, Object x) {
            return debug(name, x, empty);
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass().isArray()) {
                    out.append(name);
                    for (int i : indexes) {
                        out.printf("[%d]", i);
                    }
                    out.append("=").append("" + x);
                    out.println();
                } else {
                    indexes = Arrays.copyOf(indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(String c) {
            return append(c).println();
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class AhoCorasick {
        public int[][] next;
        public int[] fails;
        private int minChar;
        private int maxChar;
        private int allocIndicator;
        private int range;
        public int buildLast;

        public void init() {
            allocIndicator = 1;
        }

        private int alloc() {
            return allocIndicator++;
        }

        public AhoCorasick(int minChar, int maxChar, int cap) {
            this.minChar = minChar;
            this.maxChar = maxChar;
            range = maxChar - minChar + 1;
            next = new int[range][cap + 1];
            fails = new int[cap + 1];
            init();
        }

        public void prepareBuild() {
            buildLast = 0;
        }

        public void build(int c) {
            c -= minChar;
            if (next[c][buildLast] == 0) {
                next[c][buildLast] = alloc();
            }
            buildLast = next[c][buildLast];
        }

        public int[] endBuild() {
            int[] dq = new int[allocIndicator];
            int dqTail = 1;
            int dqHead = 1;
            fails[0] = -1;
            for (int i = 0; i < range; i++) {
                if (next[i][0] != 0) {
                    dq[dqTail++] = next[i][0];
                    fails[next[i][0]] = 0;
                }
            }

            while (dqHead < dqTail) {
                int head = dq[dqHead++];
                for (int i = 0; i < range; i++) {
                    if (next[i][head] != 0) {
                        dq[dqTail++] = next[i][head];
                        int fail = visit(fails[head], i);
                        if (fail == -1) {
                            fail = 0;
                        } else {
                            fail = next[i][fail];
                        }
                        fails[next[i][head]] = fail;
                    }
                }
            }

            dqTail = 1;
            dqHead = 1;
            for (int i = 0; i < range; i++) {
                if (next[i][0] != 0) {
                    dq[dqTail++] = next[i][0];
                }
            }
            while (dqHead < dqTail) {
                int head = dq[dqHead++];
                for (int i = 0; i < range; i++) {
                    if (next[i][head] != 0) {
                        dq[dqTail++] = next[i][head];
                    } else {
                        next[i][head] = next[i][fails[head]];
                    }
                }
            }

            assert dqTail == allocIndicator;
            return dq;
        }

        public int visit(int trace, int index) {
            while (trace != -1 && next[index][trace] == 0) {
                trace = fails[trace];
            }
            return trace;
        }

    }
}