明天安将参加最难的编程考试,她应该获得优异的成绩。
在最后一节理论课上,老师介绍了半回文的概念。
字符串 t 是半回文,如果对于所有奇数位置 i ($$1 \leq i \leq \frac{|t|+1}{2}$$) 满足以下条件: ti = t|t| - i + 1,其中|t|是字符串 t 的长度(如果位置从 1 开始索引)。例如,字符串“abaa”、“a”、“bb”、“abbbaa”是半回文,而字符串“ab”、“bba”和“aaabaa”则不是。
Ann 知道在考试中她将得到字符串 s,仅由字母 a 和 b 以及数字 k 组成。为了获得优异的成绩,她必须在 s 的所有半回文子串中找到字典顺序字符串中的第 k 个。请注意,按此顺序的每个子字符串都会被视为在 s 中出现的次数。
老师保证给定的数字 k 不超过给定字符串中半回文子串的数量。
你能解决这个问题吗?
输入
输入的第一行包含字符串 s (1 ≤ |s| ≤ 5000),仅由字符 'a' 和 'b' 组成,其中 |s|是字符串 s 的长度。
第二行包含一个正整数 k——给定字符串 s 的所有半回文子串中请求字符串的字典序号。字符串从 1 开始编号。
保证数字 k 不超过给定字符串中半回文子串的数量。
输出
打印给定字符串的一个子字符串,该子字符串是给定字符串的所有半回文子字符串的字典顺序中的第 k 个子字符串。
示例
输入 #1
abbabaab 7
输出 #1
abaa
输入 #2
aaaaa 10
输出 #2
aaa
输入 #3
bbaabb 13
输出 #3
bbaabb
注意
根据定义,如果 a 是 b 的前缀且与 b 不一致,或者存在这样的 i,即 a1 = b1, a2 = b2, ... ai - 1 = bi - 1, ai < bi,则字符串 a = a1a2... an 按字典顺序小于字符串 b = b1b2... bm。
在第一个示例中,半回文子字符串是以下字符串 - a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab(列表按字典顺序给出)。