计算机在分析生物数据（如 DNA 序列）方面有着重要的应用。从生物学角度来看，DNA 链是由腺嘌呤（Adenine）、胞嘧啶（Cytosine）、鸟嘌呤（Guanine）和胸腺嘧啶（Thymine）组成的核苷酸链。这四种核苷酸分别用字符 A、C、G 和 T 表示。因此，一条 DNA 链可以用由这四个字符组成的字符串来表示。我们称这样的字符串为 DNA 序列。

生物学家有时无法确定 DNA 链中的某些核苷酸。在这种情况下，字符 N 被用来表示 DNA 序列中未知的核苷酸。换句话说，N 是一个通配符，可以代表 A、C、G 或 T 中的任意一个字符。我们称包含一个或多个字符 N 的 DNA 序列为不完整序列；否则，称其为完整序列。如果一个完整序列可以通过将不完整序列中的每个 N 替换为四个核苷酸之一得到，则称该完整序列与该不完整序列相符。例如，ACCCT 与 ACNNT 相符，但 AGGAT 不相符。

研究人员通常按照英文字母表的顺序对这四种核苷酸进行排序：A 排在 C 前面，C 排在 G 前面，G 排在 T 前面。如果一个 DNA 序列中每个核苷酸都与其右侧的核苷酸相同或排在右侧核苷酸的前面，则该序列被归类为 form-1。例如，AACCGT 是 form-1，但 AACGTC 不是。

通常情况下，如果一个序列是 form-$(j-1)$，或者是一个 form-$(j-1)$ 序列与一个 form-1 序列的拼接，则称该序列为 form-$j$（其中 $j > 1$）。例如，AACCC、ACACC 和 ACACA 是 form-3，但 GCACAC 和 ACACACA 不是。

研究人员按照字典序对 DNA 序列进行排序。因此，长度为 5 的第一个 form-3 序列是 AAAAA，最后一个是 TTTTT。再举一个例子，考虑不完整序列 ACANNCNNG。与它相符的前七个 form-3 序列依次为：

ACAAACAAG ACAAACACG ACAAACAGG ACAAACCAG ACAAACCCG ACAAACCGG ACAAACCTG

任务

编写一个程序，找出与给定的长度为 $M$ 的不完整序列相符的第 $R$ 个 form-$K$ 序列。

输入格式

第一行包含三个用空格分隔的整数：$M$ ($1 \le M \le 50,000$)，$K$ ($1 \le K \le 10$) 和 $R$ ($1 \le R \le 2 \times 10^{12}$)。第二行包含一个长度为 $M$ 的字符串，即不完整序列。保证与该不完整序列相符的 form-$K$ 序列的数量不超过 $4 \times 10^{18}$，因此它可以用 C 和 C++ 中的 long long 或 Pascal 中的 Int64 表示。此外，$R$ 不超过与给定不完整序列相符的 form-$K$ 序列的总数。

输出格式

在第一行输出与输入中不完整序列相符的第 $R$ 个 form-$K$ 序列。

样例

样例输入 1

9 3 5
ACANNCNNG

样例输出 1

ACAAACCCG

样例输入 2

5 4 10
ACANN

样例输出 2

ACAGC

子任务

对于分值为 20 分的测试点，$M$ 不超过 10。