DNA Similarity

A DNA sequence consists only of the four characters A, C, G, and T. In one sequence, the distance between two characters is the number of characters between them. A subsequence is obtained by deleting zero or more characters from the original sequence.

For an integer K >= 0, a subsequence is a K-subsequence of a DNA sequence if every two adjacent characters in the subsequence have distance at most K in the original sequence. For example, in AGTCAC, the second character G and the fifth character A have T and C between them, so a subsequence that places those two characters next to each other cannot be a 1-subsequence, but it can be a 2-subsequence.

The longest common K-subsequence of two DNA sequences is the longest sequence that can be obtained as a K-subsequence from both sequences. There may be several such sequences.

For example, for AGTCAC and GATGAGAC, both AGAC and GTAC are longest common 2-subsequences. When K = 1, the longest common K-subsequences are AGC, GTA, and ATA; in lexicographic order they are AGC, ATA, GTA.

Given two DNA sequences and K, find the lexicographically smallest longest common K-subsequence.

The first line contains an integer K. K is between 0 and 30, inclusive.

The second line contains the length of the first DNA sequence. The third line contains the first DNA sequence.

The fourth line contains the length of the second DNA sequence. The fifth line contains the second DNA sequence.

Each DNA sequence has length between 1 and 1,000, inclusive, and contains no spaces between characters.

Print the longest common K-subsequence of the two given DNA sequences. If there are multiple answers, print the lexicographically smallest one.