### 问题描述 大衣有一个长度为 $N$ 的字符串 $S$ 和一个整数 $K$。 让 $C$ 表示字符串 $S$ 中所有字符的集合，如果对于字符串 $S​$ 的每个后缀子串都满足： - 集合 $C$ 中任意两个字符在后缀子串中出现次数之差不超过 $K$，或者集合 $C$ 中只包含一个字符。 则称该字符串是平衡的。 大衣想将字符串 $S$ 重新排列，得到一个平衡且字典序最小的字符串 $S'$，如果存在满足条件的字符串 $S'$ 输出该字符串，否则输出 $-1$。 ### 输入格式 第一行输入一个正整数 $T​$ 表示测试数据的组数。 接下来 $T$ 组测试数据每组输入两行： - 第一行输入两个正整数 $N,K$ 分别表示字符串的长度和集合 $C​$ 中任意两个字符在后缀子串中出现次数之差的最大值。 - 第二行输入一个长度为 $N$ 的字符串 $S$。 ### 输出格式 对于每组测试数据，如果存在满足条件的字符串 $S'$ 输出该字符串，否则输出 $-1$，并换行。 ### 样例输入 ```text 3 3 1 aaa 4 2 baba 4 1 babb ``` ### 样例输出 ```text aaa aabb -1 ``` ### 说明 样例 $1$：因为 $C=$ { $a$ }，字符串 $S$ 无论怎么排列都是是平衡的，且字典序已经最小。 样例 $2$：集合 $C=$ { $a,b$ }，考虑重新排列后的字符串 $S'=aabb$，令 $f_a,f_b$ 分别表示字符 $a,b$ 的出现次数： - 对于后缀子串 $b$，有 $f_b=1,f_a=0$，因此 $|f_b-f_a|=1\le K$。 - 对于后缀子串 $bb$，有 $f_b=2,f_a=0$，因此 $|f_b-f_a|=2\le K$。 - 对于后缀子串 $abb$，有 $f_b=2,f_a=1$，因此 $|f_b-f_a|=1\le K$。 - 对于后缀子串 $aabb$，有 $f_b=2,f_a=2$，因此 $|f_b-f_a|=0\le K$。 因此，字符串 $S'=aabb​$ 是平衡的，可以证明这是满足条件的字符串中字典序最小的。 样例 $3​$：可以证明不存在满足条件的字符串 $S'​$。 ### 评测数据规模 对于所有的评测数据，$1\le T\le 20$，$1\le N\le 10^4$，$1\le K\le N$，字符串 $S​$ 仅包含小写字母。