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:
/* Codeforces Template */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
		initTime = System.currentTimeMillis();
		try {
			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
		} catch (SecurityException e) {}
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					long prevTime = System.currentTimeMillis();
					new Main().run();
					log("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
					log("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution
	 **************************************************************/

	final int ALPHA = 26;
	
	final int UNDEFINED = -1;
	final int S1 = 0;
	final int S2 = 1;
	final int BOTH = 2;
	
	void solve() throws IOException  {
		
		final char[] s1 = in.readLine().toCharArray();
		final char[] s2 = in.readLine().toCharArray();
		final int[][] automaton = buildAutomaton(in.readLine());

		final int[][][] dp = new int [s1.length + 1][s2.length + 1][automaton.length];
		final int[][][] pr = new int [s1.length + 1][s2.length + 1][automaton.length];
		final int[][][] pp = new int [s1.length + 1][s2.length + 1][automaton.length];
		for (int[][] a : dp) for (int[] b : a) fill(b, UNDEFINED);
		for (int[][] a : pr) for (int[] b : a) fill(b, UNDEFINED);
		
		for (int pos1 = 0; pos1 < s1.length; pos1++) {
			for (int pos2 = 0; pos2 < s2.length; pos2++) {
				fill(dp[pos1][pos2], 0);
			}
		}
		
		for (int pos1 = 0; pos1 < s1.length; pos1++) {
			for (int pos2 = 0; pos2 < s2.length; pos2++) {
				for (int posV = 0; posV + 1 < automaton.length; posV++) {
					final int curValue = dp[pos1][pos2][posV];
					if (curValue == UNDEFINED) continue;
					if (s1[pos1] == s2[pos2]) {
						final int newPosV = automaton[posV][s1[pos1] - 'A'];
						if (dp[pos1 + 1][pos2 + 1][newPosV] < curValue + 1) {
							dp[pos1 + 1][pos2 + 1][newPosV] = curValue + 1;
							pr[pos1 + 1][pos2 + 1][newPosV] = BOTH;
							pp[pos1 + 1][pos2 + 1][newPosV] = posV;
						}
					}
					if (dp[pos1 + 1][pos2][posV] < curValue) {
						dp[pos1 + 1][pos2][posV] = curValue;
						pr[pos1 + 1][pos2][posV] = S1;
					}
					if (dp[pos1][pos2 + 1][posV] < curValue) {
						dp[pos1][pos2 + 1][posV] = curValue;
						pr[pos1][pos2 + 1][posV] = S2;
					}
				}
			}
		}
		
		int ansLen = -1;
		int ansPos1 = -1;
		int ansPos2 = -1;
		int ansPosV = -1;
		
		for (int pos1 = 0; pos1 <= s1.length; pos1++) {
			for (int pos2 = 0; pos2 <= s2.length; pos2++) {
				for (int posV = 0; posV + 1 < automaton.length; posV++) {
					if (ansLen < dp[pos1][pos2][posV]) {
						ansLen = dp[pos1][pos2][posV];
						ansPos1 = pos1;
						ansPos2 = pos2;
						ansPosV = posV;
					}
				}
			}
		}

		if (ansLen == 0) {
			out.println(0);
		} else {
			char[] answer = new char [ansLen];
			for (;;) {
				final int move = pr[ansPos1][ansPos2][ansPosV];
				if (move == -1) break;
				if (move == S1) {
					ansPos1--;
				} else if (move == S2) {
					ansPos2--;
				} else {
					ansPosV = pp[ansPos1][ansPos2][ansPosV];
					ansPos1--;
					ansPos2--;
					answer[--ansLen] = s1[ansPos1];
				}
			}
			out.println(answer);
		}
	}
	
	int[][] buildAutomaton(String str) {
		final char[] s = (str + "$").toCharArray();
		final int[] pi = piFunction(s);
		final int[][] automaton = new int [s.length][ALPHA];
		for (int i = 0; i < s.length; i++) {
			for (char c = 'A'; c <= 'Z'; c++) {
				final int ci = c - 'A';
				if (i > 0 && c != s[i]) {
					automaton[i][ci] = automaton[pi[i - 1]][ci];
				} else {
					automaton[i][ci] = i + (c == s[i] ? 1 : 0);
				}
			}
		}
		return automaton;
	}
	
	int[] piFunction(char[] s) {
		int n = s.length;
		int[] pi = new int [n];
		for (int i = 1; i < n; i++) {
			int j = pi[i - 1];
			while (j > 0 && s[i] != s[j])
				j = pi[j - 1];
			pi[i] = j + (s[i] == s[j] ? 1 : 0);
		}
		return pi;
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void log(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
	
	static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(long[] a, int i, int j) {
		long tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(double[] a, int i, int j) {
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void shuffle(int[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(long[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(double[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(int[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(long[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(double[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static long[] getPartialSums(int[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static long[] getPartialSums(long[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static int[] getOrderedSet(int[] a) {
		final int[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		int prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
	
	static long[] getOrderedSet(long[] a) {
		final long[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		long prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
}