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
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
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
N in the incomplete sequence with one of the four nucleotides. For example,
AGGAT does not.
Researchers often order the four nucleotides the way we order the English alphabets:
A comes before
C comes before
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,
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,
ACACA are form-, but
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 .
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.
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
Sample Input 2
5 4 10 ACANN
Sample Output 2
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 .