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 s_1, s_2 and another string called virus. Your task is to find the longest common subsequence of s_1 and s_2, such that it doesn't contain virus as a substring.


-----Input-----

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


-----Output-----

Output the longest common subsequence of s_1 and s_2 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

Difficulty: competition

Starter code:

Solutions:
# coding=utf-8
from functools import reduce

a = input()
b = input()
c = input()

alen = len(a)
blen = len(b)
clen = len(c)

kmpnext = [0]*(clen+1)
i = 1
j = 0
while i < clen:
	while j > 0 and c[i]!=c[j]:
		j = kmpnext[j]
	if c[i] == c[j]:
		j+=1
	kmpnext[i+1] = j
	i+=1
#print(kmpnext)

f = [[[0 for i in range(clen+2)] for i in range(blen+2)] for i in range(alen+2)]
g = [[[0 for i in range(clen+2)] for i in range(blen+2)] for i in range(alen+2)]
h = [[[0 for i in range(clen+2)] for i in range(blen+2)] for i in range(alen+2)]

f[0][0][0] = 0
g[0][0][0] = (-1,-1,-1)
h[0][0][0] = 1
m = (0,0,0)

for i in range(alen):
	for j in range(blen):
		for k in range(clen):
			if h[i][j][k] == 0:
				#print(i,j,k)
				continue
			if f[i+1][j][k] < f[i][j][k] or h[i+1][j][0] == 0:
				f[i+1][j][k] = f[i][j][k]
				g[i+1][j][k] = g[i][j][k]
				h[i+1][j][k] = 1
			if f[i][j+1][k] < f[i][j][k] or h[i][j+1][0] == 0:
				f[i][j+1][k] = f[i][j][k]
				g[i][j+1][k] = g[i][j][k]
				h[i][j+1][k] = 1

			if a[i] == b[j]:
				#print(i,j,a[i],b[j])
				kt = k
				while kt != 0 and a[i] != c[kt]:
					kt = kmpnext[kt]
				if a[i] == c[kt]:
					if f[i+1][j+1][kt+1] < f[i][j][k] + 1:
						f[i+1][j+1][kt+1] = f[i][j][k] + 1
						g[i+1][j+1][kt+1] = (i,j,k)
						h[i+1][j+1][kt+1] = 1
				else:
					if f[i+1][j+1][0] < f[i][j][k] + 1:
						f[i+1][j+1][0] = f[i][j][k] + 1
						g[i+1][j+1][0] = (i,j,k)
						h[i+1][j+1][0] = 1

			#print(i,j,k,f[i][j][k],g[i][j][k])

for i in range(alen+1):
	for j in range(blen+1):
		for k in range(clen):
			if f[i][j][k] > f[m[0]][m[1]][m[2]]:
				m = (i,j,k)
if f[m[0]][m[1]][m[2]] == 0:
	print(0)
else:
	ans = ""
	t = m
	t = g[t[0]][t[1]][t[2]]
	while t != (-1,-1,-1):
		ans = a[t[0]] + ans
		t = g[t[0]][t[1]][t[2]]
	print(ans)