agenti

Vecina ljudi misli da se špijuni nalaze samo u filmovima o Džejmsu Bondu. Medutim, da to nije tacno mogli su se uveriti i domaci bezbedonosni agenti koji su u jednom skladištu pronašli mašinu za kriptovanje, koju koriste strani špijuni. Oni su i ranije persretali poruke, ali nisu mogli ni da shvate kako su kriptovane. Sada su, medutim, pronašli sistem i zamolili su vas da napišete program koji ce automatski dekriptovati presretnute poruke.<br><br>

Princip rada mašine je sledeci: ulazni podataka je poruka koja se sastoji samo od malih slova latinice S1 = s1s2...sN . Mašina zatim generiše sve ciklicne permutacije S2 = s2s3...sNs1, S2 = s3s4...sNs1 s2, ..., SN = sNs1s2...sN-1 i sortira ih u leksikografskom poretku. Na ovaj nacin se dobija matrica dimenzija N?N (u i-toj vrsti matrice je i-ta po redu permutacija u sortiranom nizu permuacija, a u okviru jedne vrste elementi su pojedinacna slova u okviru permutacije koja se nalazi u toj vrsti). Kodirana poruka se sastoji od rednog broja vrste (oznacimo ga sa K) u kojoj se nalazi originalna poruka i spiska slova koja se nalaze u poslednjoj koloni matrice. Evo primera. Za poruku S1 = abracadabra imamo sledeci niz permutacija (nakon sortiranja):<br><br>

<pre>
1. aabracadabr = S11
2. abraabracad = S8
3. abracadabra = S1
4. acadabraabr = S4
5. adabraabrac = S6
6. braabracada = S9
7. bracadabraa = S2
8. cadabraabra = S5
9. dabraabraca = S7
10. raabracadab = S10
11. racadabraab = S3
</pre>
<br>
Prema tome, šifrovana poruka je: 3 rdarcaaaabb.<br><br>

Ulaz:<br>

U prvom redu standardnog ulaza nalazi se prirodan broj K (redni broj vrste matrice u kojoj se nalazi originalna poruka). U drugom redu nalazi se N (1 < N = 3500) slova koji predstavljaju zadnju kolonu matrice. Izmedu slova nema razmaka.<br><br>

Izlaz:<br>

U prvom redu standardnog izlaza treba ispisati originalnu poruku.<br><br>

Primer:<br><br>
Ulaz:<br>
3<br>
rdarcaaaabb<br><br>


Izlaz:<br>
abracadabra