Рассмотрим строку четной длины и целое число k. Строка называется k - четной тогда и только тогда, когда первая половина строки отличается от второй половины не более чем в k позициях.

Например, строка abac является 1-четной, 2-четной, но не 0-четной.

Вам задано целое число k и циклическая строка с нечетной длиной. Вы должны найти в ней k - четную подстроку максимальной длины. Отметим, что входная строка является циклической, поэтому Вы можете использовать любые ее циклические сдвиги.

Входные данные

Первая строка содержит целое число k (0 ≤ k ≤ 2000). Второй является строка из прописных латинских букв. Длина строки нечетная и не более 2000.

Выходные данные

Выведите одну строку, содержащую k - четную подстроку максимальной длины. Если таких подстрок несколько, выведите наименьшую в лексикографическом порядке. Если требуемой подстроки не существует, выведите пустую строку.