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.

输入描述:

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 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.