Comet OJ

C0460 [APIO2008-C]DNA

内存限制：256 MB 时间限制：1000 ms

题目描述

分析如 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。举例来说，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≤M≤50,000)，K(1≤K≤10)$ 和 $R(1≤R≤2×10^{12})$。第二行包含一个长度为 $M$ 的字符串，表示未完成序列。保证适合该未完成序列的范式 $-K$ 的总数不超过 $4×10^{18}$，因此该数可以用 C 和 C++中的 long long 类型表示。同时，$R$ 不会超过适合给定未完成序列的范式 $-K$ 的总数。

输出

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

样例

样例输入 1

9 3 5 
ACANNCNNG

样例输出 1

ACAAACCCG

样例输入 2

5 4 10 
ACANN

样例输出 2

ACAGC

提示

【编程提示】

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

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

【评分】

对于每组输入数据，如果你的程序输出正确便得到100%的分数，否则得0分。

在20分（20%）的测试数据中，$M$ 的值最多为 10。