Problem D
Jobb-DNA

I hundratals år har folk varit missnöjda med sina jobb. Kanske har de varit för tråkiga, för svåra, eller helt enkelt inte varit rätt av något skäl. Efter mycket forskning har JobAgent lyckats modellera hur bra du passar på jobb med hjälp av en cirkulär textsträng av längd $N$, ditt så kallade “jobb-DNA”. Varje möjligt jobb kan identifieras med en textsträng av längd $M$. Hur bra man passar på ett jobb kan sedan mätas som storleken på den största mängd förekomster av strängen i ditt jobb-DNA som inte överlappar med varandra. I strängen abbabbabba förekommer t.ex strängen abba tre gånger. Vi kan välja högst två sådana förekomster som inte överlappar (den första och sista förekomsten).

JobAgent vill gärna använda ditt jobb-DNA för att hitta det jobb som du passar bäst för. Kan du hitta textsträngen för det jobb som passar ditt jobb-DNA bäst?

Indata

Den första raden i indatan består av ett två heltal $N$ och $M$ ($2 \le M \le N \le 10^6$), längden på jobb-DNA-strängen och längden av strängen ett jobb kan identifieras med.

Den andra och sista raden innehåller en sträng med $N$ tecken a-z, ditt jobb-DNA. Notera att denna sträng är cirkulär, så att det sista tecknet i strängen åter följs av strängens första tecken.

Utdata

Skriv ut den sträng av längd $M$ som har den största mängden förekomster som inte överlappar med varandra. Om det finns flera strängar som förekommer lika många gånger, skriv ut den som kommer först i bokstavsordning.

Poängsättning

Löser du problemet fullt ut får du $2$ poäng.

För att få $1$ poäng räcker det med att du kan lösa problemet för de fall då $N \le 5\, 000$.

7 3
bcdabca

abc

11 4
abababxabax

xaba

16 4
kanomkakaomnomka

kaka