---
# System prepended metadata

title: Šifrirano sporočilo

---

# Š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`.
