Consider a string of even length and integer k. The string is called k-even 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 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.