# Šifrirano sporočilo Primožu je prijatelj poslal sporočilo, sestavljeno iz črk A in B. Primož bi ga rad razvozlal, a potrebuje tvojo pomoč. Slišal je, da se splača iskati pogoste podnize, saj so lahko povezani s pogostimi besedami v običajni slovenščini. Zato te prosi, da napišeš program, ki za podano sporočilo in število $n$ izpiše niz dolžine $n$, ki se v sporočilu največkrat pojavi (kot strnjen podniz). Štejejo tudi prekrivanja: na primer, niz `AA` v nizu `AAAA` nastopa trikrat, ne dvakrat. Če obstaja več najpogostejših nizov, potem naj program izpiše prvega po abecedi. ## Vhod V prvi vrstici je podano zaporedje $m$ črk A in B, v drugi pa število $n \in [1$, $\min(20, m)]$. ## Izhod Izpiši iskani niz. ## Omejitve vhoda * (30 točk) $m \in [1, 1000]$, $n \le 2$. * (30 točk) $m \in [1, 1000]$. * (40 točk) $m \in [1, 10^6]$. ## Primer ### Vhod ``` ABAABAABAABAA 3 ``` ### Izhod ``` ABA ``` ### Obrazložitev Niza `ABA` in `BAA` v vhodnem nizu oba nastopata po štirikrat, vendar pa je niz `ABA` po abecedi pred nizom `BAA`.