5202. Mutton string

单点时限: 1.5 sec

内存限制: 1024 MB

给定两个非空字符串 $A$ 和 $B$,同时你有一个空串$C$。

每次操作你可以选择字符串 $A$ 的一个子串,并将这个子串加到字符串 $C$ 的尾部(注意这个过程并不会改变字符串 $A$ )。

定义函数 $f(A,B)$ 为使字符串 $C$ 与字符串 $B$ 相等需要的最少操作步数,如果不能使 $C$ 和 $B$ 相等,那么 $f(A,B)=-1$。

现在给定一个长度为 $n$ 的字符串 $A$ 和两个整数 $x$, $m$,Antiamuny 想请你构造一个长度为 $m$ 的字符串 $B$ 使得 $f(A,B)=x$。

若有符合条件的串请输出字典序最小的串,否则输出”-1”。

输入格式

第一行一个整数 $T$ ($1 \leq T \leq 100$)表示数据组数。

接下来每组数据有 $2$ 行,第一行有三个整数 $n,m,x$ ($1 \leq x \leq m \leq 150 , 1 \leq n \leq 150$) ,第二行是一个长度为 $n$ 字符串 $A$ 。

输入数据保证 $\sum n, \sum m \leq 500$,所有字符串的字符均为小写字母。

输出格式

对于每组数据,输出一行长度为 $m$ 字符串表示答案。

样例

Input
4
5 3 2
aaaab
3 3 2
aab
5 3 2
aaaaa
5 3 2
cacab
Output
aba
aaa
-1
aab

28 人解决,34 人已尝试。

32 份提交通过,共有 127 份提交。

4.5 EMB 奖励。

创建: 9 月,3 周前.

修改: 9 月,3 周前.

最后提交: 8 月,2 周前.

来源: N/A

题目标签