Toistuva osajono on sellainen, joka esiintyy kahdessa (tai useammassa) kohdassa merkkijonoa. Tehtäväsi on etsiä pisin toistuva osajono annetussa merkkijonossa.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä a–z.

Tuloste

Tulosta pisin toistuva osajono. Jos ratkaisuja on monta, voit tulostaa minkä tahansa niistä. Jos merkkijonossa ei ole yhtään toistuvaa osajonoa, tulosta -1.

Rajat

• 1 \le n \le 10^5

Esimerkki

Syöte:

cabababc

Tuloste:

abab