Problem D
Job DNA
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 |
