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.