Masala E

Sizga faqat a va b harflaridan tashkil topgan satr beriladi. Sizning vazifangiz — ushbu satrga faqat a yoki b harflarini istalgan pozitsiyaga qo‘shish orqali, shunday yangi satr hosil qilish kerakki, uning hech qanday bo‘lagi (substringi) palindrom bo‘lmasin.

Palindrom deb orqadan o‘qilganda ham aynan o‘ziga teng bo‘lgan bo‘lakchaga aytiladi. Masalan: a, aa, aba, bab palindromlar hisoblanadi.

Siz satrga istalgan pozitsiyaga a yoki b harflarini qo‘shishingiz mumkin. Biroq, faqat a yoki b qo‘shishga ruxsat beriladi — boshqa harf yo‘q.

Sizdan quyidagilar talab qilinadi:

Eng kam qo‘shishlar soni bilan palindrom substringlar bo‘lmagan yangi satr hosil qiling va uni chiqaring!

Yagona satr s (1 ≤ |s| ≤ 1000) — faqat a va b harflaridan iborat.

Palindrom substringlari yo‘q qilinganidan keyingi yangi satr. Agar imkoni bo'lmasa -1 chiqaring.