5171: Ann and Half-Palindrome
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
E. Ann and Half-Palindrome
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
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: ti=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?
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: ti=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?
Input
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.
Output
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.
Examples
Input
abbabaab 7
Output
abaa
Input
aaaaa 10
Output
aaa
Input
bbaabb 13
Output
bbaabb
Note
By definition, string a=a1a2... an is lexicographically less than string b=b1b2... bm, if either a is a prefix of b and doesn't coincide with b, or there exists such i, that a1=b1,a2=b2,... ai-1=bi-1,ai<bi.
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).
输入样例 复制
输出样例 复制