Longest Common Subsequence with Required Substring

Given three numeric strings A, B and C, find a longest common subsequence (LCS) of A and B such that C appears as a contiguous substring in the LCS. If no such subsequence exists, output -1.

If there are multiple answers, any one is accepted.

Note (in LaTeX):
We are given three strings $A$, $B$, $C$. Let $S$ be a common subsequence of $A$ and $B$. We require that there exists an index \(i\) such that $$S[i\ldots i+|C|-1] = C.$$

inputFormat

The input consists of three lines. The first line contains string A, the second line contains string B and the third line contains string C. All strings consist of digits only.

outputFormat

Output a longest common subsequence of A and B that contains C as a substring. If no such subsequence exists, output -1.

sample

12345
12345
234

12345