#483. 我讨厌回文串

传统 1000 ms 1024 MiB
标准 IO
Special Judge dd 标签

题目描述

"this is not a palindromic string"

给你两个整数 n,kn,k,你需要构造一个长度为 nn 的字符串,字符串中应只含有前 kk 个小写英文字母,使得该字符串不含有长度大于等于 22 的回文子串。

子段(子串):在字符串中,任意连续的字符组合被称为该字符串的子段。例如,字符串 “hello” 的子段包括 "h", "e", "l", "o", "he", "hel", "hell", "hello" 等,但是不包括 "ho", "hllo","hl","eh" 等。

回文串:回文串又被称为回文字符串,是一种正读和反读相同的字符串,也就是从前往后读和从后往前读都是一样的。例如,"madam","racecar" 和 "level" 都是回文串。

例如,当 n=3,k=21n=3,k=21 时,字符串 "aab" 就不是一个正确的答案,因为其中含有长度为 22 的回文子串 "aa"; "aba" 也不是一个正确的答案,因为其中含有长度为 33 的回文子串 "aba"; 但是字符串 "seu" 就是一个正确的答案,因为其不含有任何大于等于 22 的回文子串。

输入格式

第一行,一个整数 t(1t104)t(1\le t \le 10^4),代表数据组数。

对于每组数据,仅一行,共两个整数 n,k(1n2105;1k26)n,k(1\le n \le 2·10^5;1\le k \le 26),代表你应该构造的字符串长度与字符集的限制。

保证同一测试点内的 n2105\sum n \le 2·10^5

输出格式

如果可以构造出一个这样的字符串,请输出一行长度为 nn 的字符串,字符串中应只含有前 kk 个小写英文字母,且该字符串不含有长度大于等于 22 的回文子串。
否则,输出 "impossible"(输出时不含有引号)。

任何满足题目要求的答案都是正确的。

样例

输入样例

7
4 26
2 19
3 20
1 1
11 18
6 20
3 2

输出样例

this
is
not
a
palindromic
string
impossible

提示
"impossible" 含有回文子串 "ss",不可能作为正确的答案。
在样例的最后一组数据中,按照题意可以构造的串为 "aaa"、"aab"、"aba"、"abb"、"baa"、"bab"、"bba"、"bbb",这些字符串全部都不满足题目要求。