DNA Sequences

One interesting task that computers help with is analyzing biological data such as DNA sequences. A single strand of DNA is a chain of the nucleotides adenine, cytosine, guanine, and thymine, denoted A, C, G, and T, respectively. A strand of DNA can therefore be written as a string over these four letters, and such a string is called a DNA sequence.

Sometimes the nucleotide at a given position on a strand cannot be determined exactly. In that case the unknown nucleotide is written with the letter N; that is, N is a wildcard that stands for any one of A, C, G, or T. A sequence that contains at least one N is called an incomplete sequence, and a sequence with no N is called a complete sequence. If each N in an incomplete sequence can be replaced by one of the four nucleotides to produce a given complete sequence, then that complete sequence is said to match the incomplete sequence. For example, ACCCT matches ACNNT, but AGGAT does not.

The four nucleotides are ordered alphabetically: A < C < G < T. A sequence is classified as type-1 if every nucleotide is equal to, or comes before, the nucleotide immediately to its right (that is, the sequence is non-decreasing from left to right). For example, AACCGT is type-1, but AACGTC is not.

In general, a type-$j$ sequence is defined as follows: a sequence is type-$j$ if it is type-$(j-1)$, or if it is the concatenation of some type-$(j-1)$ sequence and some type-1 sequence. For example, AACCC, ACACC, and ACACA are type-3, but GCACAC and ACACACA are not.

Sequences are ordered lexicographically, the same way words are ordered in a dictionary. Thus, among the type-3 sequences of length 5, the first is AAAAA and the last is TTTTT. As another example, the first seven type-3 sequences that match the incomplete sequence ACANNCNNG, in order, are:

ACAAACAAG, ACAAACACG, ACAAACAGG, ACAAACCAG, ACAAACCCG, ACAAACCGG, ACAAACCTG

Given an incomplete sequence of length $M$, write a program that finds the $R$-th type-$K$ sequence, in lexicographic order, that matches it.

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

The second line contains the incomplete sequence, a string of length $M$ consisting only of the characters A, C, G, T, and N.

The number of type-$K$ sequences that match the given incomplete sequence is at most $4 \times 10^{18}$, so it fits in a signed 64-bit integer (for example, long long in C/C++). $R$ is at most this number.

Print, on the first line, the $R$-th type-$K$ sequence in lexicographic order that matches the given incomplete sequence.