Palindroom

문제

Kevin sai informaatikaolümpiaadi eelvooru palindroomiülesande eest maksimumpunktid. Seda nähes andis õpetaja talle natuke raskema ülesande, milles uuritakse mitmesuguse pikkusega tekstilisi palindroome.

Sarnaselt arvujada juhtumiga nimetatakse teksti palindroomiks, kui see on sama eest tahapoole ja tagant ettepoole lugedes. Näiteks ABBA on palindroom (sest see on ka tagurpidi lugedes ABBA), aga ABCD ei ole (sest see on tagurpidi lugedes DCBA).

Kirjutada programm, mis leiab vähima võimaliku arvu täheasendustega viisi antud tekst palindroomiks muuta.

입력

Sisendi esimesel real on täisarv $NN$ ($1\le N\le 3001\; \backslash le\; N\; \backslash le\; 300$).

Teisel real on $NN$ suurest ladina tähest (A $\dots \backslash ldots$ Z) koosnev tekst.

출력

Väljundi esimesele reale väljastada täisarv $KK$, mis näitab, mitu tähte on minimaalselt vaja asendada, et sisendis antud tekstist saaks palindroom.

Teisele reale väljastada saadud palindroom. Kui minimaalse täheasenduste arvuga palindroome on mitu, väljastada neist (ladina tähestiku järgi) tähestikulises järjekorras esimene.