Sinulla on merkkijono, jossa on n merkkiä väliltä A–Z.

Haluat muuttaa merkkien järjestystä niin, että missään kohdassa merkkijonoa ei ole vierekkäin kahta samaa merkkiä.

Mikä on aakkosjärjestyksessä pienin tällainen merkkijono?

Syöte

Syötteen ainoalla rivillä on merkkijono.

Tuloste

Tulosta aakkosjärjestyksessä pienin haluttu merkkijono. Jos mitään ratkaisua ei ole, tulosta vain luku -1.

Rajat

• 1 \le n \le 10^6

Esimerkki 1

Syöte:

AAB

Tuloste:

ABA

Esimerkki 2

Syöte:

AAA

Tuloste:

-1