CF557E.Ann and Half-Palindrome

Tomorrow Ann takes the hardest exam of programming where she should get an excellent mark.

On the last theoretical class the teacher introduced the notion of a half-palindrome.

String t is a half-palindrome, if for all the odd positions i () the following condition is held: t__i = t|t| - i + 1, where |t| is the length of string t if positions are indexed from 1. For example, strings "abaa", "a", "bb", "abbbaa" are half-palindromes and strings "ab", "bba" and "aaabaa" are not.

Ann knows that on the exam she will get string s, consisting only of letters a and b, and number k. To get an excellent mark she has to find the k-th in the lexicographical order string among all substrings of s that are half-palyndromes. Note that each substring in this order is considered as many times as many times it occurs in s.

The teachers guarantees that the given number k doesn't exceed the number of substrings of the given string that are half-palindromes.

Can you cope with this problem?

明天，安将参加一场编程考试，这是她最艰难的一次考试，她必须取得优异的成绩。

在最后一节理论课上，老师介绍了“半回文串”（half-palindrome）的概念。

字符串 $t$ 被称为半回文串，当且仅当对所有奇数位置 $i$（），均满足如下条件：

$$t_i = t_{|t| - i + 1},$$

其中 $|t|$ 表示字符串 $t$ 的长度（位置编号从 1 开始）。例如，字符串 "abaa"、"a"、"bb"、"abbbaa" 是半回文串，而 "ab"、"bba" 和 "aaabaa" 不是。

安知道，在考试中她将获得一个仅由字母 a 和 b 组成的字符串 $s$，以及一个整数 $k$。为了取得优异成绩，她必须在 $s$ 的所有半回文子串中，找出按字典序排列的第 $k$ 个字符串。注意：每个子串在字典序列表中出现的次数，等于它在 $s$ 中作为子串出现的次数（即重复子串需重复计数）。

老师保证所给的 $k$ 不超过字符串 $s$ 中半回文子串的总数。

你能否解决这个问题？

The first line of the input contains string s (1 ≤ |s| ≤ 5000), consisting only of characters 'a' and 'b', where |s| is the length of string s.

The second line contains a positive integer k — the lexicographical number of the requested string among all the half-palindrome substrings of the given string s. The strings are numbered starting from one.

It is guaranteed that number k doesn't exceed the number of substrings of the given string that are half-palindromes.

输入的第一行包含一个字符串 $s$（$1 ≤ |s| ≤ 5000$），该字符串仅由字符 'a' 和 'b' 组成，其中 $|s|$ 表示字符串 $s$ 的长度。

第二行包含一个正整数 $k$ —— 在给定字符串 $s$ 的所有半回文子串中，按字典序排列后，所请求的字符串的序号（从 1 开始编号）。

保证 $k$ 不超过给定字符串中半回文子串的总数。

Print a substring of the given string that is the k-th in the lexicographical order of all substrings of the given string that are half-palindromes.

输出给定字符串的所有半回文子串中，按字典序排列的第 k 个子串。

By definition, string a = _a_1_a_2... a__n is lexicographically less than string b = _b_1_b_2... b__m, if either a is a prefix of b and doesn't coincide with b, or there exists such i, that _a_1 = _b_1, _a_2 = _b_2, ... a__i - 1 = b__i - 1, a__i < b__i.

In the first sample half-palindrome substrings are the following strings — a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab (the list is given in the lexicographical order).

根据定义，字符串 $a = a_1a_2\ldots a_n$ 在字典序上小于字符串 $b = b_1b_2\ldots b_m$，当且仅当以下两个条件之一成立：

• $a$ 是 $b$ 的前缀，且 $a \ne b$；
• 存在某个下标 $i$，使得 $a_1 = b_1,\, a_2 = b_2,\, \ldots,\, a_{i-1} = b_{i-1},\, a_i < b_i$。

在第一个样例中，半回文子串如下所示：a、a、a、a、aa、aba、abaa、abba、abbabaa、b、b、b、b、baab、bab、bb、bbab、bbabaab（该列表按字典序排列）。