D. Дараагийн сайн тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тэмдэгт мөртэй бодлогонд ихэнхидээ ямар нэгэн нөхцөл хангасан тэмдэгт мөр олох шаардлага гардаг. Энэ бодлогыг зохиогч тухайн чанарыг хангасан гэдгийн оронд "сайн" гэж нэрлэхээр шийджээ. Тэмдэгт мөр нь $d$-ээс их юмуу тэнцүү урттай палиндром дэд тэмдэгт мөр агуулдаг бол сайн гэе.

Чамд $s$ гэсэн Алнгли цагаан толгойн жижиг үсгүүдээс бүтэх тэмдэгт мөр өгөгднө. $s$ ээс толь бичгийн эрэмбээр том байх хамгийн бага $|s|$ урттай сайн $t$ тэмдэгт мөрийг ол.

Бид хоосон биш $s[a ... b] = s_{a}s_{a + 1}... s_{b}$ $(1 ≤ a ≤ b ≤ |s|)$ тэмдэгт мөрийг $s = s_{1}s_{2}... s_{|s|}$ тэмдэгт мөрийн дэд тэмдэгт мөр гэнэ.

Хоосон биш $s = s_{1}s_{2}... s_{n}$ тэмдэгт мөрийн хувьд $i$ бүрийн хувьд $s_{i} = s_{n - i + 1}$ биелдэг бол палиндром гэнэ. Өөрөөр хэлбэл тухайн тэмдэгт мөрийг эсрэгээр нь уншихад адилхан уншигдна гэсэн үг юм.

Хэрэв $|x| > |y|$ ба $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{|y|} = y_{|y|}$ биелдэг, эсвэл $(r < |x|, r < |y|)$ $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{r} = y_{r}$ ба $x_{r + 1} > y_{r + 1}$ байх $r$ дугаар олддог бол $x = x_{1}x_{2}... x_{|x|}$ стринг нь толь бичгийн эрэмбийн хувьд $y = y_{1}y_{2}... y_{|y|}$ стрингээс том гэгдэх юм. Мөрөндөх тэмдэгтүүд нь ASCII кодоор эрэмбэлэгдсэн шиг эрэмбэлэгднэ.

Оролт

Эхний мөрөнд $d$ ($1 ≤ d ≤ |s|$) бүхэл тоо байна.

Хоёр дахь мөрөнд хоосон биш $s$ тэмдэгт мөр байх ба урт нь $4*10^{5}$-аас хэтрэхгүй.

Гаралт

$s$ ээс толь бичгийн эрэмбээр том байх хамгийн бага $|s|$ урттай тэмдэгт мөрийг хэвлэ. Хэрэв олддоггүй бол "Impossible" гэж бичнэ үү.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
3
aaaaaaa
Гаралт
aabbcaa
Оролт
3
zzyzzzz
Гаралт
Impossible
Оролт
4
abbabbbabbb
Гаралт
abbbcaaabab
Сэтгэгдлүүдийг ачааллаж байна...