337. Keven
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 1even, 2even, but not 0even.
You are given integer
K and the cyclic string with the odd length. You are to find its
Keven 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
Keven 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.
Example(s)
sample input

sample output

1
abacaba

abaaba

sample input

sample output

2
abacaba

aabaca

sample input

sample output

0
zzz

zz
