← 返回题目列表

Codeforces · 940/C

C. 电话号码

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

电话号码在哪里?

给定一个由小写英文字母和整数 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。