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

Палиндромы 100500

Палиндромы 100500

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

Что-то давно не было задач на палиндромы, пора исправлять ситуацию. Вам дана строка s, найдите её минимальную лексикографически подстроку длины L, которая является палиндромом.

Напомним, что строка a лексикографически меньше строки b такой же длины, если существует индекс i (1i|a|), что выполняется: a_1=b_1,a_2=b_2,...,a_{i-1}_{ }=b_{i-1}, a_{i }< b_i, а палиндромом называется строка, которая читается одинаково слева направо и справа налево.

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

В первой строке находится L (1L|s|) - длина искомой подстроки. Во второй строке находится s (1|s|100500), состоящая из маленьких букв латинского алфавита.

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

Выведите минимальную лексикографически подстроку строки s, которая имеет длину L и является палиндромом. Если такой строки нет, выведите "42".

Пример

Входные данные #1
2
dccbaa
Выходные данные #1
aa
Автор Олег Петров
Источник Летняя школа Севастополь 2013, Волна 2, День 6