E. Аня и полупалиндром
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Завтра Ане предстоит сдавать самый сложный экзамен по программированию, на котором ей необходимо получить отличную оценку.

На последнем теоретическом занятии преподаватель ввел понятие полупалиндрома.

Строка t является полупалиндромом, если для всех нечетных позиций i () выполняется условие ti = t|t| - i + 1, где |t| — длина строки t, а нумерация позиций начинается с единицы. Например, строки "abaa", "a", "bb", "abbbaa" являются полупалиндромами, а строки "ab", "bba" и "aaabaa" — нет.

Аня узнала, что на экзамене она получит строку s, состоящую только из латинских символов a и b, а также число k. Для получения отличной оценки ей необходимо будет найти k-ю в лексикографическом порядке подстроку данной строки s среди тех подстрок, которые являются полупалиндромами. При этом, каждая подстрока в этом порядке учитывается столько раз, сколько раз она встречается в s.

Преподаватель гарантирует, что данное число k не превышает количества подстрок данной строки, которые являются полупалиндромами.

А вы сможете справиться с такой задачей?

Входные данные

В первой строке входных данных следует строка s (1 ≤ |s| ≤ 5000), состоящая только из символов 'a' и 'b', где |s| — длина строки s.

Во второй строке следует целое положительное число k — лексикографический номер искомой подстроки-полупалиндрома среди всех подстрок-полупалиндромов заданной строки s. Нумерация этих подстрок начинается с единицы.

Гарантируется, что число k не превышает количества подстрок данной строки, которые являются полупалиндромами.

Выходные данные

Выведите подстроку заданной строки, которая является k-й в лексикографическом порядке из тех подстрок заданной строки, которые являются полупалиндромами.

Примеры
Входные данные
abbabaab
7
Выходные данные
abaa
Входные данные
aaaaa
10
Выходные данные
aaa
Входные данные
bbaabb
13
Выходные данные
bbaabb
Примечание

По определению, строка a = a1a2... an лексикографически меньше строки b = b1b2... bm, если либо a является префиксом b и не совпадает с b, либо существует такое i, что a1 = b1, a2 = b2, ... ai - 1 = bi - 1, ai < bi.

В первом примере подстроками-полупалиндромами являются следующие строки — a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab (список задан в лексикографическом порядке).