Similarity between DNA Sequences


DNA sequences (genes) can be represented as sequences of four letters ACGT, corresponding to the four submolecules forming DNA. When biologists find a new sequence, they typically want to know what other sequences it is most similar to. One way of computing how similar two sequences are is to find the longest DNA sequence which is a subsequence of both sequences.

Problem

You are to find the longest DNA sequence which is both a subsequence of two given sequences. A subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. In some cases, the result will be the empty string. When there are more than one longest subsequence, you may break ties by selecting the one more close to the left on the first DNA sequence.

Input

The input has two lines, each containing a DNA sequence (maximum 64 characters each).

Output

The first two lines of the output contain the original ADN sequences given in the input. The third line contains the statement "Longest common sequence:" and, finally, the last line contains the longest common sequence between the two given DNA sequences. If there are no common subsequences, this fourth line is not written.

Sample Input 1

ACGGTGTCGTG
CGTTCGGCTA

Sample Output 1

ACGGTGTCGTG
CGTTCGGCTA
Longest common sequence:
CGTTCGT

Sample Input 2

ATGC
CGTA

Sample Output 2

ATGC
CGTA
Longest common sequence:
A