2236: 构造字符串
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
给定一个长度为 n 的由小写字母构成的字符串 s。
请你构造一个长度为 k 的由小写字母构成的字符串 t。
要求，字符串 t 需满足：
1.字符串 t 在字典序上大于字符串 s。
2.字符串 t 的字母集是字符串 s 的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为 {a,b,d}。
3.字符串 t 在字典序上尽可能小。
保证答案存在。
请你构造一个长度为 k 的由小写字母构成的字符串 t。
要求，字符串 t 需满足：
1.字符串 t 在字典序上大于字符串 s。
2.字符串 t 的字母集是字符串 s 的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为 {a,b,d}。
3.字符串 t 在字典序上尽可能小。
保证答案存在。
输入
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n 和 k。
第二行包含一个长度为 n 的字符串表示 s。
每组数据第一行包含两个整数 n 和 k。
第二行包含一个长度为 n 的字符串表示 s。
输出
每组数据输出一行满足所有条件的字符串 t。
样例输入 复制
4
3 3
abc
3 2
abc
3 3
ayy
2 3
ba
样例输出 复制
aca
ac
yaa
baa
提示
30%满足 1 ≤ n,k ≤ 3。
100%满足 1 ≤ T ≤ 10，1 ≤ n,k ≤ 105。
同一测试点内，所有 n 的和不超过 105，所有 k 的和不超过 105。
100%满足 1 ≤ T ≤ 10，1 ≤ n,k ≤ 105。
同一测试点内，所有 n 的和不超过 105，所有 k 的和不超过 105。