# Problem D

Job DNA

Languages
en
sv
For hundreds of years, people have been dissatisfied with
their jobs. Maybe they are too boring, too difficult or simply
not right for some reason. After much research, JobAgent has
successfully modeled how good you are at a job using a circular
string of length $N$, your
so-called “job DNA”. Each possible job can be identified with a
text string of length $M$.
How good you are at a job can then be measured as the size of
the largest set of occurrances of the job string in your job
DNA that *do not overlap* with each other. For example,
in the string `abbabbabba` the string
`abba` occurrs three times. The largest
non-overlapping set has size two and consists of the first and
last occurrence.

JobAgent wants to use your job DNA to find the job that suits you the best. Can you find the text string for the job that suits you the best?

## Input

The first line of the input consists of two integers $N$ and $M$ ($2 \le M \le N \le 10^6$), the length of the job DNA string and the length of the string that a job can be identified with.

The second and final line contains a string with
$N$ characters `a-z`, your job DNA. Note that this string is
circular, so that the last character in the string is
immediately followed by the first one.

## Output

Output the string of length $M$ with the largest non-overlapping set of occurrences in your job DNA. If there are several such strings, output the lexicographically smallest one.

## Scoring

If you solve the problem fully, you get $2$ points.

To get $1$ point, you only need to solve the problem for cases where $N \le 5\, 000$.

Sample Input 1 | Sample Output 1 |
---|---|

7 3 bcdabca |
abc |

Sample Input 2 | Sample Output 2 |
---|---|

11 4 abababxabax |
xaba |

Sample Input 3 | Sample Output 3 |
---|---|

16 4 kanomkakaomnomka |
kaka |