Abrakadabra

Uzdevums

Datu saspiešanas algoritms, kas darbojas pēc "bloku saspiešanas"metodes, pielieto datu blokiem sekojošu pārveidojumu.
Simbolu virkni P sauc par simbolu virknes S rotāciju, ja tā iegūta cikliski pārbīdot S simbolus, t.i., ja S=a₁a₂...a_N, kur a_i - virknes S i-tais elements, tad P=a_pa_p+1...a_Na₁..a_p-1, kur 1<=p<=N.

Aplūkosim tabulu M, kas sastāv no N rindām un N kolonnām, kur katrā rindā ir kāda no S rotācijām. Tabulā ir visas rotācijas, kas sakārtotas leksikogrāfiskā(vārdnīcas) secībā augošā secībā.

L ir virkne, ko veido matricas M pēdējā kolonna. Tiešais pārveidojums dotai virknei S kā rezultātu atdod virkni L un skaitli K - tās tabulas M rindas numuru, kurā ierakstīta virkne S. (Ja tādas ir vairākas, tiek atdots jebkurš no numuriem.)
Virknei S='abraka' tabula M ir sekojoša:

a		a		b		r		a		k
a		b		r		a		k		a
a		k		a		a		b		r
b		r		a		k		a		a
k		a		a		b		r		a
r		a		k		a		a		b

Virkne S atrodas tabulas otrajā rindā. L='karaab'.

Uzrakstiet programmu, kas veic apgriezto pārveidojumu - dotai virknei L un skaitlim K atrod virkni S.

Ievaddati

Teksta faila abraka.in pirmā rinda satur naturālus skaitļus K un N, kas atdalīti ar tukšumsimbolu. 1<=N<=30000, 1<=K<=N.
Faila otrā rinda satur N latīņu alfabēta mazos burtus - virkni L.

Izvaddati

Teksta faila abraka.out vienīgajā rindā jāizvada virkne S.

Piemērs

abraka.in	abraka.out
2 6 karaab	abraka

Atsauces