Merkkijonon reuna on merkkijono, joka on merkkijonon alkuosa ja loppuosa ja joka ei ole merkkijono itse. Esimerkiksi merkkijonon acbdacb reuna on acb.

Tehtäväsi on selvittää annetun merkkijonon pisin reuna.

Syöte

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

Voit olettaa, että merkkijonon reuna ei ole tyhjä.

Tuloste

Tulosta merkkijonon reuna.

Rajat

• $1 \le n \le 10^6$

Esimerkki

Syöte:

acbdacb

Tuloste:

acb