题目描述

给定一个长度为 $n$ 的由小写字母构成的字符串 $s$。

请你构造一个长度为 $k$ 的由小写字母构成的字符串 $t$。

要求，字符串 $t$ 需满足：

• 字符串 $t$ 在字典序上大于字符串 $s$。

• 字符串 $t$ 的字母集是字符串 $s$ 的字母集的子集。一个字符串的字母集是指该字符串包含的所有不同字母的集合，例如 abadaba 的字母集为 {a,b,d}。

• 字符串 $t$ 在字典序上尽可能小。

保证答案存在。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $n$ 和 $k$。

第二行包含一个长度为 $n$ 的字符串表示 $s$。

输出格式

每组数据输出一行满足所有条件的字符串 $t$。

样例

4 
3 3 
abc 
3 2 
abc 
3 3 
ayy 
2 3 
ba

aca 
ac 
yaa 
baa

提示

$1\\le T \\le 10$，

$1\\le n,k \\le 10^5$。

同一测试点内，所有 $n$ 的和不超过 $10^5$，所有 $k$ 的和不超过 $10^5$。

来源：Acwing

转录 By QLU_钟志强