Завтра Ане предстоит сдавать самый сложный экзамен по программированию, на котором ей необходимо получить отличную оценку.
На последнем теоретическом занятии преподаватель ввел понятие полупалиндрома.
Строка t является полупалиндромом, если для всех нечетных позиций i (
) выполняется условие ti = t|t| - i + 1, где |t| — длина строки t, а нумерация позиций начинается с единицы. Например, строки "abaa", "a", "bb", "abbbaa" являются полупалиндромами, а строки "ab", "bba" и "aaabaa" — нет.
Аня узнала, что на экзамене она получит строку s, состоящую только из латинских символов a и b, а также число k. Для получения отличной оценки ей необходимо будет найти k-ю в лексикографическом порядке подстроку данной строки s среди тех подстрок, которые являются полупалиндромами. При этом, каждая подстрока в этом порядке учитывается столько раз, сколько раз она встречается в s.
Преподаватель гарантирует, что данное число k не превышает количества подстрок данной строки, которые являются полупалиндромами.
А вы сможете справиться с такой задачей?
Выходные данные
Выведите подстроку заданной строки, которая является k-й в лексикографическом порядке из тех подстрок заданной строки, которые являются полупалиндромами.
Примечание
По определению, строка 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 (список задан в лексикографическом порядке).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
abbabaab
7
|
abaa
|
|
2
|
aaaaa
10
|
aaa
|
|
3
|
bbaabb
13
|
bbaabb
|