【问题描述】
qiyue平时训练就很喜欢写串串的题目，有一天他学到了一种新的数据结构叫回文树，能一次性找出一个串里的所有回文子串，他觉得很开心，就跑去找kangdi聊天去了，kangdi：“我觉得你这个数据结构不错，不过都2019年了怎么还有人看回文串这种无趣的东西呢……这样子吧，我希望你能扩展一下这个数据结构，找到一个串中所有不完全回文子串。”qiyue:”那是啥…”kangdi:“我们设一个串T的长度为|t|，则一个不完全回文子串指的是对于一个串中前半部分奇数位置i（ (|t|+1)/2>=i>=1 ） T中的第i个位置字符和第|t|-i+1个字符都相等的串，比如"abaa", "a", "bb", "abbbaa",“aaa”就是不完全回文子串，"ab", "bba" and "aaabaa"，就啥也不是，我感觉这样的子串挺多的，你别一一列出来了，我只想问你字典序第k小的串是啥,如果一个子串出现了多次就统计多次”qiyue感觉这个问题他没啥头绪，你能帮帮他吗?
字典序：对于两个字符串，显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。
【输入形式】
第一行输入一个字符串 字符串长度不超过4000，输入仅有a,b两种字符，由于qiyue不太会造数据，所以数据随机生成。
【输出形式】
输入一个整数k，代表询问字典序第k小子串(保证字符串中不完全回文子串不超过k个)
【样例输入1】
aaaaaaa
20
【样例输出1】
aaaa
【样例输入2】
aaabababab
15
【样例输出2】
aba
【样例输入3】
abaa
6
【样例输出3】
abaa
【时间和空间限制】
时间限制：4s
空间限制：512MB
| 难度等级： | 0 |
| 总通过次数： | 0 |
| 总提交次数： | 6 |