Description

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

Sometimes biologists cannot determine certain nucleotides in a single-stranded DNA. In such cases, the character N is used to denote an undetermined nucleotide. In other words, N can represent any one of A, C, G, or T. We call a DNA sequence that contains one or more N an incomplete sequence; otherwise, it is called a complete sequence. If a complete sequence can be obtained by arbitrarily replacing each N in an incomplete sequence with A, C, G, or T, then the complete sequence is said to be compatible with this incomplete sequence. For example, ACCCT is compatible with ACNNT, but AGGAT is not.

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

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

Similarly, researchers sort DNA sequences in lexicographic order. Under this definition, the smallest DNA sequence belonging to form-3 is AAAAA, and the largest is TTTTT. Here is another example. Consider the incomplete sequence ACANNCNNG. Then the first 7 DNA sequences compatible with this incomplete sequence are:

ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

Input Format

The first line contains three integers separated by spaces: M ($1 \le M \le 50{,}000$), K ($1 \le K \le 10$), and R ($1 \le R \le 2 \times 10^{12}$).

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

It is guaranteed that the total number of form-K sequences compatible with the given incomplete sequence does not exceed $4 \times 10^{18}$; therefore, this number fits in type long long in C/C++ or Int64 in Pascal. Also, R will not exceed the total number of form-K sequences compatible with the given incomplete sequence.

Description

Input Format

Output Format

Output the R-th form-K sequence that is compatible with the given incomplete sequence on the first line.

9 3 5 
ACANNCNNG

ACAAACCCG

5 4 10 
ACANN

ACAGC 

Hint

Translated by ChatGPT 5