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 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.

Example(s)
sample input
sample output
1
abacaba
abaaba

sample input
sample output
2
abacaba
aabaca

sample input
sample output
0
zzz
zz




Online Contester Team © 2002 - 2010. All rights reserved.