Lucky Common Subsequence

3000ms

524288K

Description:

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

Input:

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

Output:

Output the longest common subsequence of s₁ and s₂ 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.

Sample Input:

AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ

Sample Output:

ORZ

Sample Input:

AA
A
A

Sample Output:

Informação

Provedor Codeforces

Código CF346B