На телевидении всегда были популярны интеллектуальные шоу, в которых участники меряются своими умственными способностями, отвечая на сложные вопросы из различных областей. Вы решили создать свою викторину. Но самое сложное — не подготовить вопросы (их легко найти в Интернете), а сделать шоу красочным для зрителей. Поэтому гвоздь Вашей программы — огромный вращающийся барабан, разделённый на n секторов. В каждом секторе написана одна строчная буква латинского алфавита, обозначающая категорию вопроса. Барабан вращается только по часовой стрелке. Для удобства на одном из секторов нарисована стрелка, показывающая направление вращения.

Итак, вопросы составлены и разделены на категории, барабан готов, приглашения трём друзьям разосланы. И в самый последний момент Вам приходит мысль: буквы должны быть записаны на барабане не как попало, а в определённом порядке, чтобы было красивее! Подбежав к барабану, Вы начинаете его вращать, пытаясь найти хоть какой-нибудь узор.

Будем говорить, что барабан имеет период p (p > 0), если буква на каждом секторе совпадает с буквой на секторе, отстоящем на p позиций в направлении вращения. Барабан может иметь несколько периодов; в частности, барабан всегда имеет период n, так как секторов всего n. Вас интересует минимальный период. До начала шоу осталось всего ничего, и у Вас есть время поменять не более k букв, чтобы минимальный период был как можно меньше.

Определите наименьший возможный период, который может получиться у барабана после замены не более k букв.

В первой строке через пробел даны два целых числа n и k — количество секторов на барабане и наибольшее количество букв, которое можно заменить (1 ≤ n ≤ 10⁵; 0 ≤ k ≤ n).

Во второй строке записано n строчных латинских букв — буквы, записанные на барабане, начиная с отмеченного стрелкой сектора в направлении вращения барабана.

В первой строке выведите одно число — наименьший положительный период, который может получиться у барабана.

Во второй строке выведите n строчных латинских букв — буквы, которые будут записаны на барабане после замены. Выводите буквы в том же порядке: начиная с отмеченного стрелкой сектора в направлении вращения. Использовать все k замен не обязательно.