题目描述

对于一个长度为偶数的字符串和整数 $K$，若字符串前一半与后一半对应位置不同的字符数不超过 $K$，则称该字符串为 K-even。

例如 abac 是 1-even、2-even，但不是 0-even。

给定整数 $K$ 和一个长度为奇数的循环字符串。你可以从任意循环移位后的位置开始截取子串。请找出长度最大的 K-even 子串；若有多个长度最大的答案，输出其中字典序最小的一个。

输入格式

第一行一个整数 $K$，$0\le K\le2000$。

第二行一个仅由小写英文字母组成的字符串 $s$。$|s|$ 为奇数且 $|s|<2000$。

输出格式

输出一行，为最长的 K-even 循环子串；若有多个，输出字典序最小者。若不存在任何非空 K-even 子串，则输出一个空行。

样例 1

1
abacaba

abaaba

样例 2

2
abacaba

aabaca

样例 3

0
zzz

zz