DNA Translation

Deoxyribonucleic acid (DNA) is a sequence of nucleotide bases paired together to form a double-stranded helix. Through a series of biochemical processes, the nucleotide sequences in an organism's DNA are translated into the proteins it needs to live. Your task is to write a program that accepts a DNA strand and reports the protein it generates, if any.

DNA is built from four nucleotide bases: adenine, cytosine, guanine, and thymine (written A, C, G, and T). These bases bond in a chain to form one half of a DNA strand. The other half is a similar chain in which each base is replaced by its complement: A and T are complementary, and C and G are complementary. The two half-strands bond through these complementary pairs to form the full double strand.

A DNA strand is usually written by listing only the bases of the primary strand; the complementary strand is obtained by writing the complement of each base. For example, the strand TACTCGTAATTCACT has the complement ATGAGCATTAAGTGA (A always pairs with T, and C with G).

From a primary DNA strand, a messenger RNA (mRNA) strand is produced by transcription. The transcribed mRNA is identical to the complementary DNA strand, except that thymine (T) is replaced by uracil (U). For example, the mRNA for the strand above is AUGAGCAUUAAGUGA.

The sequence of bases in the mRNA determines which protein is synthesized. The mRNA is read as consecutive codons of exactly three bases each. The codon AUG marks the start of a protein, and any of the codons UAA, UAG, or UGA marks its end. The one or more codons strictly between the start and the stop codon are the amino acids of the protein. For example, AGC is serine (Ser), AUU is isoleucine (Ile), and AAG is lysine (Lys), so the mRNA above encodes the protein Ser-Ile-Lys.

The full genetic code is shown below (only amino-acid abbreviations are listed, and Stop marks a termination codon). Note that AUG, already identified as the start codon, also codes for methionine (Met): the first AUG in an mRNA strand is the start, but every later AUG is translated normally as Met. In the table, the leftmost column gives the first base of the codon, the four columns headed U, C, A, and G give the second base, and the rightmost column gives the third base.

The input consists of DNA strands, one strand per line, and is terminated by a line containing a single asterisk (*). For each strand you must determine and output the protein it generates, if any.

The given strand may be the primary strand or the complementary strand, and it may be written in either forward or reverse order; the start and stop sequences do not necessarily appear at the ends of the strand. Therefore each strand must be examined under all four interpretations — as written, reversed, complemented, and reverse-complemented — replacing T with U in each case to obtain a candidate mRNA. For example, any of ATACTCGTAATTCACTCC, CCTCACTTAATGCTCATA, TATGAGCATTAAGTGAGG, or GGAGTGAATTACGAGTAT yields the protein Ser-Ile-Lys.

Every strand contains only the uppercase DNA bases A, C, G, and T. No line exceeds 255 characters, and there are no blank lines or spaces in the input.

For each input strand, output on its own line the protein it encodes, written as the hyphen-separated list of amino-acid abbreviations (for example, Ser-Ile-Lys).

To read a candidate mRNA, scan it from left to right for the first start codon AUG. Starting just after that AUG, read successive three-base codons until the first stop codon (UAA, UAG, or UGA). The amino acids of those codons, in order, form the protein; a valid protein must contain at least one amino acid and must reach a stop codon.

Some strands are valid DNA but do not encode a valid protein. If none of a strand's four interpretations yields a valid protein, output the line *** No translatable DNA found ***.

If more than one of the four interpretations yields a valid protein, output the lexicographically greatest of those protein strings, comparing them as ordinary text (ASCII order). This makes the answer for each strand unique.