题目描述

分析如 \(DNA\) 序列这样的生命科学数据是计算机的一个有趣应用。从生物学的角度上说， \(DNA\) 是一种由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶这四种核苷酸组成的链式结构。这四种核苷酸分别用大写字母 \(A\)、\(C\)、\(G\)、\(T\) 表示。这样，一条 \(DNA\) 单链可以被表示为一个只含以上四种字符的字符串。我们将这样的字符串称作一个 \(DNA\) 序列。

有时生物学家可能无法确定一条 \(DNA\) 单链中的某些核苷酸。在这种情况下，字符 \(N\) 将被用来表示一个不确定的核苷酸。换句话说，\(N\) 可以用来表示 \(A\)、\(C\)、\(G\)、\(T\) 中的任何一个字符。我们称包含一个或者多个 \(N\) 的 \(DNA\) 序列为未完成序列；反之，就称作完成序列。如果一个完成序列可以通过将一个未完成序列中的每个 \(N\) 任意替换成A、C、G、T得到的话，就称完成序列适合这个未完成序列。举例来说，\(ACCCT\) 适合 \(ACNNT\)，但是\(AGGAT\) 不适合。

研究者们经常按照如下方式排序四种核苷酸：

• \(A\) 优先于 \(C\)，
• \(C\) 优先于 \(G\)，
• \(G\) 优先于 \(T\)。

如果一个 \(DNA\) 序列中的每个核苷酸都与其右边的相同或者优先，就将其归类为 范式-1 (form-1)。举例来说，\(AACCGT\) 是 范式-1，但是 \(AACGTC\) 不是。

一般来说，一个 \(DNA\) 序列属于 范式-j (\(j>1\))，只要它属于 范式-(j-1) 或者是一个 范式-(j-1) 和一个 范式-1 的连接。举例来说，\(AACCC\)、\(ACACC\) 和 \(ACACA\) 都是 范式-3，但 \(GCACAC\) 和 \(ACACACA\) 不是。

同样，研究者们按照字典序对 \(DNA\) 序列进行排序。按照这个定义，最小的属于 范式-3 的 \(DNA\) 序列是 \(AAAAA\)，最大的是 \(TTTTT\)。这里是另外一个例子，考虑未完成序列 \(ACANNCNNG\)。那么前 \(7\) 个适合这个未完成序列的 \(DNA\) 序列是：

ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG

写一个程序，找到按字典序的第 \(R\) 个适合给定的长度为 \(M\) 的未完成序列的 范式-K。

输入

第一行，包含三个由空格隔开的整数：\(M\)(\(1 \leq M \leq 5 \times 10^4\)),\(K\)(\(1 \leq K \leq 10\)),\(R\)(\(1 \leq R \leq 2 \times 10^{12}\))。

第二行，包含一个长度为 \(M\) 的字符串，表示未完成序列。保证适合该未完成序列的 范式-K 的总数不超过 \(4 \times 10^{18}\)，因此该数可以用 C 和 C++ 中的 long long 类型或者 Pascal 中的 Int64 类型表示。
同时，\(R\) 不会超过适合给定未完成序列的 范式-K 的总数。

输出

在第一行中输出第 \(R\) 个适合输入中的未完成序列的 范式-K。

样例 1

输入

9 3 5
ACANNCNNG

输出

ACAAACCCG

样例 2

输入

5 4 10
ACANN

输出

ACAGC

数据范围限制

对于每组输入数据，如果你的程序输出正确便得到 \(100\%\) 的分数，否则得0分。
在20分（20%）的测试数据中，\(M\) 的值最多为 10。

提示

在 C 和 C++中，你应该使用 long long 数据类型。
下面的程序片断给出了如何从标准输入中读写 long long：

long long a;
scanf("%lld",&a);
printf("%lld\n",a);

在 Pascal 中，你应该使用 Int64 类型。

来源

APIO2008