Problem Description

Analyzing life science data such as DNA sequences is an interesting application of computers. From a biological perspective, DNA is a chain structure composed of four nucleotides: adenine, cytosine, guanine, and thymine. These four nucleotides are represented by the capital letters A, C, G, and T, respectively. Thus, a single strand of DNA can be represented as a string containing only these four characters. We call such a string a DNA sequence.

Sometimes, a biologist may not be able to determine some nucleotides in a DNA single strand. In this case, the character N is used to represent an uncertain nucleotide. In other words, N can represent any of A, C, G, or T. We call a DNA sequence containing one or more Ns an incomplete sequence; otherwise, it is called a complete sequence. If a complete sequence can be obtained by replacing any N in an incomplete sequence with A, C, G, or T, we say the complete sequence fits the incomplete sequence. For example, ACCCT fits ACNNT, but AGGAT does not.

Researchers often order the four nucleotides as follows: A precedes C, C precedes G, and G precedes T. If every nucleotide in a DNA sequence is the same or precedes the one to its right, we classify it as pattern-1. For example, AACCGT is pattern-1, but AACGTC is not.

Generally, a DNA sequence belongs to pattern-j (j>1) if it belongs to pattern-(j-1) or is a concatenation of a pattern-(j-1) and a pattern-1. For example, AACCC, ACACC, and ACACA are all pattern-3, but GCACAC and ACACACA are not.

Similarly, researchers sort DNA sequences lexicographically. By this definition, the smallest pattern-3 DNA sequence is AAAAA, and the largest is TTTTT. Here is another example, considering the incomplete sequence ACANNCNNG. The first 7 DNA sequences that fit this incomplete sequence are:

ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

Input Format

The first line of input contains three integers separated by spaces: M (1≤M≤50,000), K (1≤K≤10), and R (1≤R≤2×10^12).

The second line contains a string of length M representing the incomplete sequence.

It is guaranteed that the total number of pattern-K sequences that fit this incomplete sequence does not exceed 4×10^18, so this number can be represented by a long long type in C and C++, or an Int64 type in Pascal. Also, R will not exceed the total number of pattern-K sequences that fit the given incomplete sequence.

Output Format

Output the R-th pattern-K sequence that fits the incomplete sequence from the input on the first line.

Sample Input and Output

Sample Input #1

9 3 5 
ACANNCNNG

Sample Output #1

ACAAACCCG

Sample Input #2

5 4 10 
ACANN

Sample Output #2

ACAGC

见题面 Input 部分

见题面 Output 部分