Tarkastellaan seuraavaa merkkijonon salaustapaa:

1. lisää merkkijonon loppuun merkki #, joka on pienempi kuin kaikki aakkoston merkit
2. muodosta kaikki merkkijonon kierrot
3. järjestä kierrot aakkosjärjestykseen
4. muodosta tämän järjestyksen perusteella uusi merkkijono, jossa on jokaisen kierron viimeinen merkki

Esimerkiksi merkkijonosta MAIJA tulee MAIJA#. Sen kierrot ovat järjestyksessä #MAIJA, A#MAIJ, AIJA#M, IJA#MA, JA#MAI, MAIJA#. Kun luetaan järjestyksessä kiertojen viimeiset merkit, syntyy merkkijono AJMAI#.

Syöte

Syötteen ainoalla rivillä on salattu merkkijono, jossa on n+1 merkkiä (yksi merkki # ja muut merkit väliltä A–Z).

Tuloste

Tulosta alkuperäinen merkkijono, jossa on n merkkiä.

Rajat

• 1 \le n \le 10^6

Esimerkki

Syöte:

AJMAI#

Tuloste:

MAIJA