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:
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class LuckyCommonSubsequence {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        char[] s1 = "_".concat(sc.next()).toCharArray();
        char[] s2 = "_".concat(sc.next()).toCharArray();
        char[] virus = "_".concat(sc.next()).toCharArray();

        int[] restart = new int[virus.length];
        // prefrestartixTable[i] stores the longest prefix that can be slid to i and
        // match perfectly that ISN'T ITSELF
        restart[1] = 0; // base case
        for (int i = 2; i < virus.length;) {
            int j = restart[i - 1];
            // j is the end of last strictly smaller prefix, and we can append to it
            while (j > 0 && virus[i] != virus[j + 1]) {
                j = restart[j];
            }
            // j is less than i by definition.
            if (virus[i] != virus[j + 1]) {
                i++;
            }
            else {
                while (i < virus.length && virus[i] == virus[j + 1]) {
                    restart[i] = j + 1;
                    i++;
                    j++;
                }
            }
        }
        /*
AABABABAAABABAAABAAAABAABABAABABAABAABAAAABAABAAAABAAAABAABBAABAAAABAABABAABABAABAAAA
ABAABABABAAABAAAABBAABAAAABABAABABAAABAABAAAABABAAAAAABAAAAABAAAAABABAAAAAABABAABAAAA
AA
AA
AB
         */
//        System.out.println(Arrays.toString(virus));
//        System.out.println(Arrays.toString(restart));
        int S1 = s1.length - 1, S2 = s2.length - 1, V = virus.length - 1;
        int[][][] dp = new int[S1 + 1][S2 + 1][V];
        State[][][] trans = new State[S1 + 1][S2 + 1][V];
        // track what we used to arrive at a certain state (length of how far we've
        // gone in each string
        // 0 is increased i to get here, 1 is j, 2 is increased both
        // virus pos should never reach V - 1
        for (int i = 0; i <= S1; i++) {
            for (int j = 0; j <= S2; j++) {
                Arrays.fill(trans[i][j], new State(-1, -1, -1, false, false));
            }
        }
        trans[0][0][0] = new State(-1, -1, -1, true, false);
        for (int i = 0; i <= S1; i++) {
            for (int j = 0; j <= S2; j++) {
                for (int v = 0; v <= V - 1; v++) {
                    // don't take
                    // Need equal signs in transitions, since we are allowed to just keep the same!
                    if (i > 0 && trans[i - 1][j][v].reached && dp[i - 1][j][v] >= dp[i][j][v]) {
                        dp[i][j][v] = dp[i - 1][j][v];
                        trans[i][j][v] = new State(i - 1, j, v, true, false);
                    }
                    if (j > 0 && trans[i][j - 1][v].reached && dp[i][j - 1][v] >= dp[i][j][v]) {
                        dp[i][j][v] = dp[i][j - 1][v];
                        trans[i][j][v] = new State(i, j - 1, v, true, false);
                    }
                    // take!
                    if (i > 0 && j > 0 && s1[i] == s2[j]) {
                        // we can only arrive to something with positive length of virus substring
                        if (v > 0 && s1[i] == virus[v] && trans[i - 1][j - 1][v - 1].reached && 1 + dp[i - 1][j - 1][v - 1] >= dp[i][j][v]) {
                            dp[i][j][v] = 1 + dp[i - 1][j - 1][v - 1];
                            trans[i][j][v] = new State(i - 1, j - 1, v - 1, true, true);
                        }
                        if (s1[i] != virus[v + 1] && trans[i - 1][j - 1][v].reached) {
                            // if the next character in virus matches this one, it's bad!
                            // not the old character! This is a different transition style (push, since we pushing different cases
                            // to reach 0. The other transition pulled smaller states to add the next virus letter)

                            // whoah. use the string prefix function to maximize the substring at the end of us,
                            // after adding this character
                            int pos = v;
                            while (pos > 0 && virus[pos + 1] != s1[i]) {
                                pos = restart[pos];
                                // we get to the length of that restart, +1 since we added this matching thing
                            }
                            if (virus[pos + 1] != s1[i]) {
                                pos = -1;
                                // pos + 1 = 0, meaning we have no length
                            }
                            if (1 + dp[i - 1][j - 1][v] >= dp[i][j][pos + 1]) {
                                dp[i][j][pos + 1] = 1 + dp[i - 1][j - 1][v];
                                trans[i][j][pos + 1] = new State(i - 1, j - 1, v, true, true);
                            }
                        }
                        // this is a separate case, we can transition in a special way from any v value, to 0!
                    }
                }
            }
        }
        State bestState = new State(-1, -1, -1, false, false);
        int bestVal = 0;
        for (int i = 0; i <= S1; i++) {
            for (int j = 0; j <= S2; j++) {
                for (int v = 0; v <= V - 1; v++) {
                    if (dp[i][j][v] > bestVal) {
                        bestVal = dp[i][j][v];
                        bestState = new State(i, j, v, true, false);
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        State curr = bestState;
        while (curr.i > 0 && curr.j > 0) {
            State next = trans[curr.i][curr.j][curr.v];
            if (next.take) {
                sb.append(s1[curr.i]);
            }
            curr = next;
        }
        out.println(sb.length() == 0 ? 0 : sb.reverse());
        out.close();
    }

    static class State {
        int i, j, v;
        boolean reached, take;
        public State(int ii, int jj, int vv, boolean rr, boolean tt) {
            i = ii; j = jj; v = vv; reached = rr; take = tt;
        }

        public String toString() {
            return "Prev = " + i + ", " + j + ", " + v + " take = " + take;
        }
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
}