Maksimum Palindrom

Hüseyn bu dəfə dostu Azərə doğum günü münasibətilə üzərində palindrom söz yazılmış hədiyyə verməyi planlayır. Lakin hədiyyənin dəyərli olması üçün bu sözün leksikoqrafik cəhətdən mümkün qədər böyük olmasını istəyir.

Hazırda hədiyyənin üzərində kiçik ingilis hərflərindən ibarət $s$ sözü yazılıb. $s$ palindrom olmaya bilər, lakin Hüseynin verəcəyi hədiyyədə yazılan söz mütləq palindrom olmalıdır, yoxsa Azər hədiyyədən heç də məmnun qalmayacaq.

Hüseyn $s$ sözündə hər hansı hərfi başqa bir kiçik ingilis hərfilə əvəz edə bilər. Bu onun $1$ dəqiqəsini alır. O bunu ən çox $k$ dəfə edə bilər, çünki $k$ dəqiqədən sonra hədiyyəni Azərə təqdim edəcək.

Hüseynin Azərə verəcəyi hədiyyənin üzərinə yaza biləcəyi leksikoqrafik cəhətdən ən böyük palindrom sözü tapın. Əgər Hüseyn palindrom söz düzəldə bilməyəcəksə çıxışa :( verin.

Qeyd 1. Əvvəldən axıra və axırdan əvvələ eyni oxunan sözlərə palindrom sözlər deyilir. Məsələn, radar sözü palindromdur, lakin rfo palindrom deyil.

Qeyd 2. Eyni uzunluqlu $x$ sözü $y$ sözündən leksikoqrafik cəhətdən o zaman böyük sayılır ki, elə $i$ var ki, $i$-ci simvoldan qabaq hər iki söz eynidir, lakin $x$-in $i$-ci simvolu $y$-in $i$-ci simvolundan böyükdür.

Giriş verilənləri

Birinci sətirdə kiçik ingilis hərflərindən ibarət $s(1\le |s|\le 10^5)$ sözü, növbəti sətirdə isə $k(0\le k\le |s|)$ tam ədədi verilir.

Çıxış verilənləri

Çıxışa Hüseynin Azərə verəcəyi hədiyyənin üzərinə yaza biləcəyi leksikoqrafik cəhətdən ən böyük palindrom sözü, əgər bu mümkün deyilsə :( verin.

Nümunələr