Задачі
Паліндроми 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}".
Вхідні дані #1
2 dccbaa
Вихідні дані #1
aa