Time limit per test: 0.25 second(s) Memory limit: 65536 kilobytes
input: standard output: standard
Consider a string of even length and integer K. The string is called if and only if the first half of the string differs from the second half in no more than K positions.
For example, string
abac
is 1-even, 2-even, but not 0-even.
You are given integer K and the cyclic string with the odd length. You are to find its K-even substring of the maximal length. Note, input string is cyclic, so you can use any of its cyclic shifts.
Input
The first line of the input file contains integer K (0 ≤ K ≤ 2000). The second line contains string of small Latin letters. The length of the string is odd and it is less than 2000.
Output
Print single line containing K-even substring of the maximal length. If there are several such substrings, print the smallest in lexicographical order. If such substring does not exist, print one blank line.