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