← 返回题目列表

Codeforces · 1924/A

A. 我们是否涵盖了所有内容?

中文机器翻译题面 查看原题

给你两个整数 $$$n$$$ 和 $$$k$$$ 以及一个字符串 $$$s$$$。

你的任务是检查使用前 $$$k$$$ 小写英文字母组成的所有可能的长度为 $$$n$$$ 的字符串是否作为 $$$s$$$ 的子序列出现。如果答案是否定的,您还需要打印一个长度为 $$$n$$$ 的字符串,该字符串可以使用前 $$$k$$$ 小写英文字母组成,该字母不会作为 $$$s$$$ 的子序列出现。

如果有多个答案,您可以打印其中任何一个。

注意:如果可以通过从 $$$b$$$ 中删除一些(可能为零)字符而不改变剩余字符的顺序来获得 $$$a$$$,则字符串 $$$a$$$ 称为另一个字符串 $$$b$$$ 的子序列。

输入

输入的第一行包含一个整数$$$t \, (1 \le t \le 10^5)$$$,测试用例的数量。

每个测试用例的第一行包含 $$$3$$$ 整数 $$$n \, (1 \le n \le 26), \: k \, (1 \le k \le 26), \: m \, (1 \le m \le 1000)$$$,其中 $$$n$$$ 和 $$$k$$$ 与输入中描述的相同,$$$m$$$是字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$m$$$的单个字符串$$$s$$$,仅包含前$$$k$$$小写英文字母。

保证所有测试用例的 $$$m$$$ 之和与 $$$n$$$ 之和不超过 $$$10^6$$$。

输出

对于每个测试用例,如果使用前 $$$k$$$ 小写英文字母组成的所有可能的长度为 $$$n$$$ 的字符串都作为 $$$s$$$ 的子序列出现,则打印 YES,否则打印 NO。

如果您的答案是否定的,请打印一个长度为 $$$n$$$ 的字符串,该字符串可以使用前 $$$k$$$ 小写英文字母组成,该字母不会作为 $$$s$$$ 的子序列出现在下一行中。

在任何情况下,您都可以打印 YES 或 NO 的每个字母(例如 YES、yES、YeS 都将被识别为肯定答案)。

示例

输入 #1

3
2 2 4
abba
2 2 3
abb
3 3 10
aabbccabab

输出 #1

YES
NO
aa
NO
ccc

注意

对于第一个测试用例,使用前 $$$2$$$ 英语字母表可以形成的长度为 $$$2$$$ 的所有可能的字符串 (aa, ab, ba, bb) 都作为 abba 的子序列出现。

对于第二个测试用例,字符串 aa 不是 abb 的子序列。