电话号码在哪里?
给定一个由小写英文字母和整数 k 组成的字符串 s。找到长度为 k 的字典顺序最小字符串 t,使其字母集是 s 字母集的子集,并且 s 按字典顺序小于 t。
保证答案存在。
请注意,字母集是一个集合,而不是多重集。例如,abadaba的字母集合是{a,b,d}。
字符串 p 按字典顺序小于字符串 q,如果 p 是 q 的前缀,不等于 q 或存在 i,使得 pi < qi 并且对于所有 j < i,满足 pj = qj。例如, abc 按字典顺序小于 abcd , abd 按字典顺序小于 abec , afa 按字典顺序不小于 ab , a 不按字典顺序小于 a 。
输入
输入的第一行包含两个空格分隔的整数 n 和 k (1 ≤ n, k ≤ 100 000) - s 的长度和 t 所需的长度。
输入的第二行包含由n个小写英文字母组成的字符串s。
输出
输出符合上述要求的字符串t。
保证答案存在。
示例
输入 #1
3 3 abc
输出 #1
aca
输入 #2
3 2 abc
输出 #2
ac
输入 #3
3 3 ayy
输出 #3
yaa
输入#4
2 3 ba
输出#4
baa
注意
在第一个示例中,长度为 3 的字符串 t 列表(使得 t 的字母集是 s 的字母子集)如下:aaa、aab、aac、aba、abb、abc、aca、acb、...。其中,按字典顺序排列的大于 abc:aca、acb、...。其中按字典顺序排列最小的是 aca。