DNA         dna.X

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 N characters 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 alphabet: A precedes C, C precedes G, and G precedes T. A
DNA sequence is classified as Form-1 if every nucleotide in it is
the same as or precedes the nucleotide immediately to its right.
For example, AACCGT is Form-1, but AACGTC is not.

In general, a sequence is Form-j for j > 1 if it is a form-(j-1)
or it is a concatenation of a form-(j-1) sequence and a form-1
sequence. For example, AACCC, ACACC, and ACACA are form-3, 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-3 sequence of length 5 is AAAAA, and the
last is TTTTT. As another example, consider the incomplete sequence
ACANNCNNG. The first seven Form-3 sequences that agree with it are:
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

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

PROBLEM NAME: dna

INPUT FORMAT:

* Line 1: Three integers separated by one space: 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, which is the incomplete
        sequence. It is guaranteed that the number of form-K sequences
        that agrees with the incomplete sequence is not greater than
        4*10^18, so it can be represented by a long long in C and C++.
        Moreover, R does not exceed the number of form-K sequences that 
        agree with the given incomplete sequence.

* Line 2: A single word of length M that is the basis for agreement

SAMPLE INPUT (file dna.in):

9 3 5
ACANNCNNG

OUTPUT FORMAT:

* Line 1: The Rth form-K sequence that agrees with the incomplete
        sequence in the input.

SAMPLE OUTPUT:

ACAAACCCG