Palindrom je riječ za koju je svejedno čitamo li ju slijeva nadesno ili zdesna nalijevo. Primjeri palindroma su "kisik" i "abba".</p>

Dvije riječi su anagrami ako se promjenom poretka slova jedne riječi može dobiti druga. Na primjer, riječi "kanonada" i "anakonda" su anagrami.

Riječ je anadrom ako je anagram nekog palindroma. Tako su "p", "abab" i "sikki" anadromi, dok "papagaj" i "anakonda" nisu.

Svaka riječ može se rastaviti na podriječi (podnizovi uzastopnih slova početne riječi) koje su anadromi. Za zadanu riječ, potrebno je odrediti rastav na anadrome koji se sastoji od najmanjeg broja podriječi.

입력 형식

Na ulazu se nalazi jedna riječ, niz malih slova engleske abecede. Riječ će se sastojati od najviše 10000 slova. 

출력 형식

Jedini red izlaza se treba sastojati od niza riječi odvojenih jednim razmakom. Za niz treba vrijediti:</p>

• Spajanjem svih riječi dobiva se ulazna riječ.
• Svaka riječ u nizu je anadrom.
• Ne postoji rastav s manjim brojem riječi koji zadovoljava prva dva uvjeta.

Rješenje ne mora biti jedinstveno. Dovoljno je ispisati bilo koji rastav koji zadovoljava sve uvjete. 

예제 입력 1

ababcd

예제 출력 1

ababc d

예제 입력 2

abcdabcd

예제 출력 2

abcdabcd

예제 입력 3

abcdab

예제 출력 3

a b c d a b