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.*;
import java.util.*;

public class B implements Runnable{
	public static void main (String[] args) {new Thread(null, new B(), "_cf", 1 << 28).start();}

	char[] s1, s2, virus;
	int n, m, k;
	int[][][] dp, ptr;
	AhoCorasick ac;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		s1 = fs.next().toCharArray(); n = s1.length;
		s2 = fs.next().toCharArray(); m = s2.length;
		virus = fs.next().toCharArray(); k = virus.length;
		ac = new AhoCorasick(); ac.build(new String[] {new String(virus)});
		dp = new int[n][m][k];
		ptr = new int[n][m][k];
		for(int[][] dd : dp)
			for(int[] d : dd)
				Arrays.fill(d, -1);
		int len = solve(0, 0, 0);
		if(len == 0) {
			System.out.println(len);
			return;
		}
		int p1 = 0, p2 = 0, p3 = 0;
		char[] res = new char[len];
		for(int i = 0; i < len; i++) {
			int type = ptr[p1][p2][p3];
			if(type == 1) {
				res[i] = s1[p1];
				p3 = ac.trie[s1[p1]-'A'][p3];
				p1++; p2++;
			}
			else if(type == 2) {
				p1++; i--;
			}
			else if(type == 3) {
				p2++; i--;
			}
			else {
				System.out.println(1/0);
			}
		}
		out.println(new String(res));
		out.close();
	}
	
	int solve(int p1, int p2, int p3) {
		if(ac.end[p3] == 1) return -1;
		if(p2 == m || p1 == n) return 0;
		int res = dp[p1][p2][p3];
		if(res != -1) return res;
		res = 0;
		
		if(s1[p1] == s2[p2]) {
			int np3 = p3;
			np3 = ac.trie[s1[p1]-'A'][np3];
			int ret = solve(p1+1, p2+1, np3);
			if(ret >= 0 && 1+ret > res) {
				res = Math.max(res, 1+ret);
				ptr[p1][p2][p3] = 1;
			}
		}
		int ret = solve(p1+1, p2, p3);
		if(ret >= 0 && ret > res) {
			res = Math.max(res, ret);
			ptr[p1][p2][p3] = 2;
		}
		ret = solve(p1, p2+1, p3);
		if(ret >= 0 && ret > res) {
			res = Math.max(res, ret);
			ptr[p1][p2][p3] = 3;
		}
		
		return dp[p1][p2][p3] = res;
	}
	
	class AhoCorasick {
		int[][] trie;
		int[] fail, end;
		int maxNodes, curNode, ALPHA = 26;
		
		void build(String[] pats) {
			int n = pats.length;
			maxNodes = 1;
			for(String s : pats) maxNodes += s.length();
			trie = new int[ALPHA][maxNodes];
			end = new int[maxNodes];
			curNode = 1;
			
			for(int i = 0; i < n; i++) {
				String s = pats[i];
				int at = 0;
				for(char c : s.toCharArray()) {
					int idx = c-'A';
					if(trie[idx][at] == 0) trie[idx][at] = curNode++;
					at = trie[idx][at];
				}
				end[at] = 1;
			}
			
			fail = new int[curNode];
			int[] queue = new int[curNode];
			int tail = 1;
			for(int i = 0; i < tail; i++) {
				int node = queue[i];
				int link = fail[node];
				if(node != link) {
					//build suffix link tree here
				}
				
				for(int idx = 0; idx < ALPHA; idx++) {
					if(trie[idx][node] != 0) {
						if(node == 0) fail[trie[idx][node]] = 0;
						else fail[trie[idx][node]] = trie[idx][link];
						queue[tail++] = trie[idx][node];
					}
					else {
						if(node == 0) trie[idx][node] = 0;
						else trie[idx][node] = trie[idx][link];
					}
				}
				
			}
			
		}
		
	}


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

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

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			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 long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

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

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

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

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}