Salakirjoitus

• Time limit: 1.00 s
• Memory limit: 128 MB

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