## APIO '08 P3 - DNA

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

One interesting use of computer is to analyze biological data such as DNA sequences. Biologically, a strand of DNA is a chain of nucleotides Adenine, Cytosine, Guanine, and Thymine. The four nucleotides are represented by characters A, C, G, and T, respectively. Thus, a strand of DNA can be represented by a string of these four characters. We call such a string a DNA sequence.

It is possible that the biologists cannot determine some nucleotides in a DNA strand. In such a case, the character N is used to represent an unknown nucleotides in the DNA sequence of the strand. In other words, N is a wildcard character for any one character among A, C, G or T. We call a DNA sequence with one or more character N an incomplete sequence; otherwise, it is called a complete sequence. A complete sequence is said to agree with an incomplete sequence if it is a result of substituting each N in the incomplete sequence with one of the four nucleotides. For example, ACCCT agrees with ACNNT, but AGGAT does not.

Researchers often order the four nucleotides the way we order the English alphabets: A comes before C, C comes before G, G comes before T. A DNA sequence is classified as form-1 if every nucleotide in it is the same as or comes before the nucleotides immediately to its right. For example, AACCGT is form-, but AACGTC is not.

In general, a sequence is form-j, for , if it is a form-() or it is a concatenation of a form-() sequence and a form- sequence. For example, AACCC, ACACC, and ACACA are form-, but GCACAC and ACACACA are not.

Again, researchers order DNA sequences lexicographically the way we order words in a dictionary. As such, the first form- sequence of length is AAAAA, and the last is TTTTT. As another example, consider the incomplete sequence ACANNCNNG. The first seven form- sequences that agree with it are:

Write a program to find the th form- sequence that agrees with the given incomplete sequence of length .

#### Input

The first line contains three integers separated by one space: , and The second line contains a string of length , which is the incomplete sequence. It is guaranteed that the number of form- sequences that agrees with the incomplete sequence is not greater than Moreover, does not exceed the number of form- sequences that agree with the given incomplete sequence.

#### Output

On the first line, print the th form- sequence that agrees with the incomplete sequence in the input.

#### Sample Input 1

9 3 5
ACANNCNNG

#### Sample Output 1

ACAAACCCG

#### Sample Input 2

5 4 10
ACANN

#### Sample Output 2

ACAGC

#### Scoring

The score for each input scenario will be if the correct answer is outputted and otherwise.

In test scenarios worth points, will be at most .