为了辅助你的研究，Bakhyt 提供了一个 DNA 字典——一种存储了 $N$ 个 DNA 字符串的数据结构。DNA 字符串是长度为 $K$ 的字符串，仅由大写字母 ‘A’、‘C’、‘G’ 和 ‘T’ 组成。
不幸的是，这个字典的接口很奇怪，你需要找到一种正确使用它的方法。
该字典允许你使用模板访问其数据。模板是一个长度为 $K$ 的字符串，可以包含三种类型的字符：大写字母 ACGT、问号和下划线。对于给定的模板，字典会检查其所有 DNA 字符串是否与模板匹配，并告知匹配字符串的相关信息。如果字符串 $S$ 在每个位置 $i$ ($1 \le i \le K$) 都与模板 $T$ 匹配（$T_i$ 为下划线的位置除外），则称 $S$ 与模板 $T$ 匹配。位置上的匹配规则如下：
- ‘A’、‘C’、‘G’、‘T’ —— 如果 $T_i$ 是这些字母之一，则仅当 $S_i$ 等于 $T_i$ 时，该位置匹配。
- ‘?’ —— 如果 $T_i$ 是问号，则无论 $S$ 如何，该位置均匹配。
该字典仅有一个函数：
get_min_max(T)—— 查找与给定模板 $T$ 匹配的字典中字典序最小和最大的字符串。
模板中的下划线表示该位置在检查过程中会被完全忽略。get_min_max(T) 返回的字符串在 $T$ 包含下划线的位置处也会包含下划线。
你需要找到一种方法，对于任意给定的 DNA 字符串，确定字典中按字母顺序排列在其之后（或等于它）的字符串。
交互
你的提交不得从标准输入读取数据、向标准输出打印数据或与任何其他文件交互。
你需要实现以下函数：
string find_next(string P)
- $P$ 是一个长度为 $K$ 的 DNA 字符串。
- 该函数必须返回字典中字典序大于或等于 $P$ 的最小字符串。
- 如果不存在这样的字符串，函数必须返回一个空字符串。
你可以调用以下函数：
pair <string, string> get_min_max(string T)
- $T$ 是一个长度为 $K$ 的模板字符串。
- 该函数将返回字典中与模板 $T$ 匹配的字典序最小和最大的字符串对，且在 $T$ 包含下划线的位置处返回下划线。
- 如果没有字符串与模板匹配，函数将返回一对空字符串。
在每个测试用例中，你总共最多可以进行 2500 次函数调用。如果违反了上述任何条件，你的程序将获得 Wrong Answer 判决。否则，你的程序将获得 Accepted 判决，你的得分将根据 get_min_max 函数的调用总次数以及所有调用中参数包含的问号总数来计算（请参阅“子任务”部分）。
子任务
在本任务中，评测机不是自适应的。这意味着字典的内容在运行开始时是固定的，不依赖于你程序的调用。
本任务包含两个子任务：
- (10 分) $K = 4$。
- (90 分) $K = 256, N \le 2 \times K$。在此子任务中，你的得分计算方式如下：
设 $q$ 为调用
get_min_max函数的总次数，$m$ 为所有调用中get_min_max参数所使用的问号总数。则你的得分计算如下：- 如果 $q + m \ge 2500$，得分为 0。
- 如果 $q + m \le 550$，得分为 90。
- 如果 $550 < q + m < 2500$，得分按公式 $\frac{2500-(q+m)}{2500-550} \cdot 90$ 计算。
注意，该子任务的最终得分为你在所有测试点中得分的最小值。
说明
样例评测机按以下格式读取输入：
- 第 1 行：$N, K$
- 第 2 行：$S_1, S_2, ..., S_n$
你可以在系统中下载 dnadict.zip，其中包含 Java 和 C++11 语言的示例。
上述内容中包含了所有函数调用的示例。
dnadict.zip 包含每种语言的解决方案示例。
对于 Java 语言的解决方案，文件和类名必须分别命名为 Dnadict.java 和 Dnadict。