Fișierul intrare/ieșire	bart.in, bart.out	Sursă	ad-hoc
Autor	clasică	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.05 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Bart (clasele 9-10)

Bart Simpson a făcut o nouă poznă. Drept pedeapsă, învățătoarea lui l-a pus să scrie pe tablă, de nenumărate ori, un mesaj. Bart l-a scris de câteva ori, apoi s-a plictisit și a fugit pe geam. Prietenul său, Milhouse, intrând în sala de clasă și uitându-se la tablă, s-a întrebat: ce mesaj a avut Bart de scris?

Ajutați-l pe Milhouse să recupereze mesajul original. Dacă există mai multe variante, Milhouse o vrea pe cea mai scurtă. Ultima repetiție a mesajului poate fi incompletă.

Date de intrare

Fișierul de intrare bart.in conține o singură linie, conținând șirul de pe tablă (N litere mari și mici ale alfabetului latin, urmate de \n).

Date de ieșire

În fișierul de ieșire bart.out se va scrie mesajul cu lungime minimă pe care, dacă îl copiem de un număr (nu neapărat întreg) de ori, obținem șirul de pe tablă.

Restricții

• 1 ≤ N ≤ 500.000

Exemplu

Explicație

Pentru al doilea exemplu și abababbabababb, repetat de două ori, produce șirul inițial. Este preferat abababb, repetat de patru ori, pentru că este mai scurt.