问题描述
一个字符串被称为square当且仅当它可以由两个相同的串连接而成. 例如, "abab", "aa"是square, 而"aaa", "abba"不是.
两个长度相同字符串之间的hamming distance是对应位置上字符不同的位数.
Alex有个偶数长度的字符串$s=s_{1}s_{2}...s_{n}$. 他想要找到一个字典序最小的square $t=t_{1}t_{2}...t_{n}$ 使得$s$和$t$之间的hamming distance恰好是$m$. 另外, $s$和$t$仅包含小写英文字母.
输入描述
输入包含多组数据, 第一行包含一个整数$T$ $(1 \le T \le 500)$表示测试数据组数. 对于每组数据:
第一行包含两个整数$n$和$m$ $(1 \le n \le 1000, 0 \le m \le n, n \text{ is even})$表示字符串的长度和hamming distance. 第二行包含一个字符串$s$.
输出描述
对于每组数据, 如果不存在这样的一个square, 输出"Impossible" (不包含引号). 否则, 输出字典序最小的square.
输入样例
3
4 1
abcd
4 2
abcd
4 2
abab
输出样例
Impossible
abab
aaaa
