Merkkijonon jakso on alkuosa, jota toistamalla merkkijono muodostuu. Viimeinen toistokerta voi olla osittainen.

Esimerkiksi merkkijonon acbacbac lyhin jakso on acb.

Tehtäväsi on etsiä syötteenä annetun merkkijonon lyhin jakso.

Syöte

Syötteenä on merkkijono, jossa on n merkkiä ja jokainen merkki on välillä a–z.

Tuloste

Tulosta merkkijonon lyhin jakso.

Rajat

• 1 \le n \le 10^6

Esimerkki

Syöte:

acbacbac

Tuloste:

acb