Adapted from Genome sequencing by Phillip E. C. Compeau, and prepared by Ibrahim Mesecan
You are working on a genome project. Gene sequences use nucleic acid sequences from the composition: GACT. You are given a genome fragments, and you are asked to merge them. Gene fragments are merged in such a way that, if the last m nucleic acid sequences of gene fragment A matches with the first m nucleic acid sequence of B. These gene fragments A and B can be merged. For example, if m is 2 and you are given TAA as starting gene then you are also given the following nucleic acid sequences: ATG, TGC, TGC, AAACT, AAT and CCG. TAA can be merged with AAT and form TAAT. TAAT is ending with AT and thus it can be merged with ATG and form the sequence TAATG. Then similarly, TAATGC can be formed.

Question: Write a program that reads n gene fragments and after sorting gene fragments, using Sequential search on the sorted list finds the matching sequence. By adding the sequences one after another forms the longest DNA sequence.

Input specification: You will be two integers in the beginning,

• number of gene fragments (n): an integer between 1 and 10,000,
• the number nucleic acids used in merge process (m): an integer between 1 and 20

Output specification: Show the fragment which was formed.

Explanation: TAA is the starting DNA fragment, ending with AA. There are two gene fragments starting with AA: AAACT and AAT. Using Sequential search AAACT has been selected as the second gene fragment. Now the new gene fragment is TAAACT, ending with CT. There is only one gene fragment starting with CT: CTG. So, the new gene TAAACTG and it is merged with TGC.