Problems
Палиндромы 100500
Палиндромы 100500
Что-то давно не было задач на палиндромы, пора исправлять ситуацию. Вам дана строка \textbf{s}, найдите её минимальную лексикографически подстроку длины \textbf{L}, которая является палиндромом.
Напомним, что строка \textbf{a} лексикографически меньше строки \textbf{b} такой же длины, если существует индекс \textbf{i} (\textbf{1} ≤ \textbf{i} ≤ \textbf{|a|}), что выполняется: \textbf{a_1=b_1,} \textbf{a_2=b_2,} \textbf{...,} \textbf{a}_\{i-1\}_\{ \}\textbf{=} \textbf{b}_\{i-1\}, \textbf{a}_\{i \}< \textbf{b_i}, а палиндромом называется строка, которая читается одинаково слева направо и справа налево.
\InputFile
В первой строке находится \textbf{L} (\textbf{1} ≤ \textbf{L} ≤ \textbf{|s|}) - длина искомой подстроки. Во второй строке находится \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{100500}), состоящая из маленьких букв латинского алфавита.
\OutputFile
Выведите минимальную лексикографически подстроку строки \textbf{s}, которая имеет длину \textbf{L} и является палиндромом. Если такой строки нет, выведите "\textbf{42}".
Input example #1
2 dccbaa
Output example #1
aa