eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

K-четная

K-четная

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Рассмотрим строку четной длины и целое число k. Строка называется k - четной тогда и только тогда, когда первая половина строки отличается от второй половины не более чем в k позициях.

Например, строка abac является 1-четной, 2-четной, но не 0-четной.

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

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

Первая строка содержит целое число k (0k2000). Второй является строка из прописных латинских букв. Длина строки нечетная и не более 2000.

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

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

Пример

Входные данные #1
1
abacaba
Выходные данные #1
abaaba
Входные данные #2
2
abacaba
Выходные данные #2
aabaca
Входные данные #3
0
zzz
Выходные данные #3
zz
Источник 2007 Петрозаводск, Saratov for Karelia with love, Январь 28, Задача B