Problem D
Annorlunda Anagram

Du får givet en sträng bestående av $N$ bokstäver, där $N$ är jämnt. Hitta ett sätt att kasta om bokstäverna i strängen så att samtliga $N/2+1$ delsträngar av längd $N/2$ blir olika.

Indata

En rad med en sträng $S$ av längd $N$ ($2\le N\le {10}^5$, $N$ är jämnt). Strängen innehåller bokstäver från “a” till “z”.

Utdata

Om det är möjligt att kasta om bokstäverna, skriv ut en sträng av samma längd som indatan, som är en omkastning av bokstäverna sådan att alla delsträngar av längd $N/2$ är olika. Om det är omöjligt, skriv ut $-1$.

Om det finns flera lösningar kan du skriva ut vilken som helst.

Förklaring av exempel

I det första exemplet är delsträngarna innan omkastning “tral”, “rala”, “alal”, “lala”, och “alal”. Här förekommer “alal” två gånger vilket inte är OK, däremot efter omkastning är alla delsträngarna olika.

I det tredje exemplet är alla delsträngar olika från början så det räcker med att skriva ut den ursprungliga strängen.

tralalal

allatral

zzzz

-1

annorlunda

annorlunda