You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

西西酱正在准备 CSP 2077 的初赛模拟题，共有 $N$ 道单选题，每道题的选项为大写字母 'A' 到 'F'。

现在她已经设计好了每道题的答案，可以用长度为 $N$ 的字符串 $S$ 表示。

经过细心观察，西西酱发现，她班上的小朋友做题全靠蒙！

更具体的，每位小朋友都会临时构造一个长度不超过 $K$ 的字符串，仅包含大写字母 'A' 到 'F'，作为答题的模式串。

如果字符串的长度为 $L$，则对于前 $L$ 题，就按字符串中的字符依次作答，如果还有后续题目，就循环使用该字符串作答。

换句话说，对于第 $L + 1$ 题，使用第 $1$ 个字符作答，对于第 $L + 2$ 题，使用第 $2$ 个字符作答，以此类推。

• 例如某次考试有 $10$ 道题，而某位小朋友生成的字符串为 "ABC"，则他就会按照 "ABCABCABCA" 的次序作答。

西西酱想知道，对于所有可能的模式串，哪个模式串能答对最多的题目呢？找到并输出最优的模式串，如果存在多个最优模式串，则输出字典序最小的一个。

输入格式

第一行两个整数 $N$, $K$，表示题目的数量，以及模式串的长度上限。

第二行一个长度为 $N$ 的字符串 $S$，表示每道题的答案。

输出格式

输出一行，一个字符串，表示字典序最小的最优模式串。

12 5
AACAAACBAACA

AACA

该模式串可以答对 $12$ 道题中的 $11$ 题，是最优模式串的唯一解。

19 4
FCFBFAFDFEFCFBFEFDF

FAFB

该模式串可以答对 $12$ 道题，其他模式串（例如 "FB"、"FC"）也可以答对 $12$ 题，但该字符串是字典序最小的一个。

【样例 3】

pattern3.in pattern3.ans

【样例 4】

pattern4.in pattern4.ans

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le K \le N \le 5000$，字符串 $S$ 中仅包含 'A' 到 'F' 之间的大写字母。