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 PYTHON):

Solution:
'''
References:
KMP (string matching):
    CLRS Ch. 32.4
    http://www.cse.ust.hk/~dekai/271/notes/L16/L16.ps

The idea of the back pointer is strongly recommended by professor Huang.
The code is built based on Codeforce solution examples for the problem:
Case#   Author
6164370 IcedCoffee
5323729 lucaslima
'''
import sys
from collections import defaultdict
from time import time
from random import randint

##if len(sys.argv) != 2:
##    sys.stderr.write('usage: {0} [file]\n'.format(sys.argv[0]))
##    sys.exit(1)

def kmp_calculate_next(pattern):
    pattern = '0' + pattern
    m = len(pattern)
##        print pattern, m
    next = [0]*(m)
    next[0] = -1
    k = 0       #k represents the number of characters found as a match so far

    for q in xrange(2, m):
##        print 'Before q=',q,'k=',k
        while k > 0 and pattern[k+1] != pattern[q]:
##                print 'Before q=',q,'k=',k,'pattern[k]=',pattern[k],'pattern[q]=',pattern[q]
            k = next[k]
##                print 'After  q=',q,'k=',k,'pattern[k]=',pattern[k],'pattern[q]=',pattern[q]
            
        if pattern[k+1] == pattern[q]:
            k = k + 1
        
        next[q] = k

##    print next
    return next 

def get_next(index, c):
    while (index >= 0 and c != virus[index]):
##        print virus[index] , 'vs' , c
        index = next_state[index]
    index = index + 1
##    print index
    return index


memoize = True

def lucky(i, j, k):
    if memoize and (i, j, k) in opt:
        return opt[i, j, k]
    if k == len(virus):
        #when '-inf' is returned, the last letter in virus won't get added in output
        return float("-inf")
    if i == len(s1) or j == len(s2):
        #normally, we see i == 0 or j == 0 as bases cases. Here, we flip it the other way around.
        #since we don't know at the start of the program where k will end up,
        #the normal top down approach has to be modified where top down still starts
        #from [0,0,0] for the recursive calls
        return 0
    if s1[i] == s2[j]:
        new_k = get_next(k, s1[i])
        opt[i, j, k] = lucky(i+1, j+1, new_k) + 1
##        print opt[i, j, k]
        if opt[i, j, k] > 0:
            forward[i, j, k] = (1, i+1, j+1, new_k)
    if lucky(i+1, j, k) > opt[i, j, k]:
        opt[i, j, k] = opt[i+1, j, k]
        forward[i, j, k] = (2, i+1, j, k)
    if lucky(i, j+1, k) > opt[i, j, k]:
        opt[i, j, k] = opt[i, j+1, k]
        forward[i, j, k] = (3, i, j+1, k)
    return opt[i, j, k]

def backtrace(i, j, k):
    if i == len(s1) or j == len(s2):
        return ""
    if forward[i, j, k] == 0:
        return ""
##    print 'forward[', i, j, k, ']=', forward[i, j, k]
    direction, new_i, new_j, new_k = forward[i, j, k]
    if direction == 1:
        return s1[i] + backtrace(new_i, new_j, new_k)
    return backtrace(new_i, new_j, new_k)

input = [raw_input() for _ in xrange(3)]
s1, s2, virus = [line.strip() for line in input]
##s1="ABABC"
##s2="ABABC"
##virus="ABC"
##s1="AXBPBDEYIYKKCZBTLKBUNEQLCXXLKIUTOOATYDXYYQCLFAXAEIGTFMNTTQKCQRMEEFRYVYXAOLMUQNPJBMFBUGVXFZAJSBXWALSI"
##s2="VWFONLLKSHGHHQSFBBFWTXAITPUKNDANOCLMNFTAAMJVDLXYPILPCJCFWTNBQWEOMMXHRYHEGBJIVSXBBGQKXRIYNZFIWSZPPUUM"
##virus="PPKKLHXWWT"
##s1="AJKEQSLOBSROFGZ"
##s2="OVGURWZLWVLUXTH"
##virus="OZ"
##s1='ABABABB'
##s2='ABABABB'
##virus='ABABB'
##s1='ABBB'
##s2='ABBB'
##virus='ABB'
##s1='QNHRPFYMAAPJDUHBAEXNEEZSTMYHVGQPYKNMVKMBVSVLIYGUVMJHEFLJEPIWFHSLISTGOKRXNMSCXYKMAXBPKCOCNTIRPCUEPHXM'
##s2='RRFCZUGFDRKKMQTOETNELXMEWGOCDHFKIXOPVHHEWTCDNXVFKFKTKNWKEIKTCMHMHDNCLLVQSGKHBCDDYVVVQIRPZEOPUGQUGRHH'
##virus='R'
##    virus='ABABABABCA'
##    virus='ABABACA'
##    virus='ABABABC'
##    virus='ABB'
##    virus='abcdabc'
##    virus='abcdabcb'
##    virus='abcdabcc'
##    virus='abcdabcdd'
##    virus='abcdabcdabcdd'
##print len(s1), len(s2), len(virus)
####with open(sys.argv[1]) as f:
####    for line in f:
####        s1, s2, virus = line.split()    
####        ##opt = defaultdict(lambda : defaultdict(lambda : defaultdict(int)))
####        opt = defaultdict(int)  # opt[i, j, k] instead of opt[i][j][k]
####        forward = defaultdict(int) #default: 0
####        next_state = kmp_calculate_next(virus)
####        print lucky(0, 0, 0)
####        result = backtrace(0, 0, 0)
####        print '0' if result == "" else result
##t = time()
##print lcs(len(x), len(y))
##print "time:", time() - t
##print opt
##print "non-zero cells:", len(opt)
####f.close()

opt = defaultdict(int)  # opt[i, j, k] instead of opt[i][j][k]
forward = defaultdict(int) #default: 0
next_state = kmp_calculate_next(virus)
lucky(0, 0, 0)
result = backtrace(0, 0, 0)
print '0' if result == "" else result
##for i in range(0, len(s1)+1):
##    for j in range(0, len(s2)+1):
##        for k in range (0, len(virus)+1):
####            if opt[i,j,k] != 0:
##            print 'opt[', i, j, k, ']=', opt[i,j,k]
##for i in range(0, len(s1)+1):
##    for j in range(0, len(s2)+1):
##        for k in range (0, len(virus)+1):
##            if forward[i,j,k] != 0:
##                print 'forward[', i, j, k, ']=', forward[i,j,k]