Codeforces Round 311 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

graphs

string suffix structures

strings

trees

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Ann and Half-Palindrome

time limit per test

1.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputTomorrow 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?

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* = *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).

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 15:24:49 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|