On television, shows that challenge people to intellectual games have always been popular. So you decided to create your own quiz show. The most difficult part isn’t coming up with questions (they can be easily found online), but making the show visually appealing for viewers. That’s why the main decoration of your show is a giant rotating wheel divided into n sectors. Each sector contains one lowercase English letter, denoting a category of a question. The wheel can only be rotated clockwise. For convenience, one sector has an arrow on it, showing the direction of rotation.

The questions are prepared and categorized, the wheel is ready, and the invitations are sent to three of your friends. Suddenly, a brilliant idea comes to you mind: letters should be written not randomly, but in a pattern! You rush to the wheel and start rotating it, trying to make out at least some pattern.

Let’s say that the wheel has a period p (p > 0), if the letter on each sector is the same as the letter on the sector p positions further in the direction of rotation. The wheel might have multiple periods; in particular, it always has a period n, since there are n sectors in total. The show is about to start, so you have time to change at most k letters to minimize the period of the wheel.

Determine the smallest period possible that the wheel can have after you change up to k letters.

The first line contains two integers, separated with spaces: n and k — the amount of sectors on the wheel and the amount of letters you can replace (1 ≤ n ≤ 10⁵; 0 ≤ k ≤ n).

The second line contains n lowercase English letters — letters written on the wheel, starting from the sector with an arrow. Letters are read in the direction of rotation of the wheel.

In the first line, output a single integer — the smallest positive period the wheel can have after you change up to k letters.

In the second line, output n lowercase English letters — letters written on the wheel after you change them, starting from the sector with an arrow. Letters are read in the direction of rotation of the wheel. You don’t have to use all k replacements.