Repeat Repeat

Pablo the Duck likes to duplicate strings. Specifically, on his days off, he will take some starting string of length $N$ and then repeat it $M$ times, forming the string $S$ which will have length $N \times M$. For example, Pablo could have started with the string "ABBC" and repeating it 3 times would give "ABBCABBCABBC".

However, one tragic day, Pablo dropped his string, which randomly flipped some of the characters, giving the broken string $T$. Pablo has forgotten what the original string $S$ was, and would like it back so he has come to you for help.

Given $N$, $M$ and $T$ what is the minimum number of characters in $T$ you need to replace to form a plausible guess for $S$? A guess is considered plausible if it can be constructed by repeating some string of length $N$, $M$ times. For extra points, output a plausible guess for $S$.

Input

The first line will contain two space-separated integers, $N$ and $M$.

The second line will contain the string $T$, of length $N\times M$. It will consist only of the uppercase letters A through Z.

Output

On a single line, output a single integer $X$, the minimum number of characters you must replace to form a plausible string $S$.

Optionally, for extra points, on the second line, output a plausible string $S$ that can be formed by replacing $X$ characters in $T$. It must consist only of the uppercase letters A through Z. See the scoring section for more details.

Constraints

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le N\times M \le 10^5$
• $S$ and $T$ consists only of uppercase letters A through Z.

Subtasks

• Subtask 1 (10%): $N \times M \le 100$
• Subtask 2 (15%): $M = 2$
• Subtask 3 (15%): $N = 1$
• Subtask 4 (20%): $T$ consists only of uppercase letters A or B.
• Subtask 5 (40%): No further constraints

Scoring

On any testcase:

• If you output $X$ correctly, but output an incorrect guess (or no guess at all) of the string $S$, you will get 80% of the points for that testcase.
• If you output $X$ correctly, and output a valid guess of the string $S$, you will get 100% of the points for that testcase.

Your score for a subtask is the amount of points available for that subtask multiplied by the lowest percentage score you got on any of the testcases in that subtask.

Sample Explanations

Sample 1

We can replace the fourth and tenth characters in ABCFABCDAECD to form ABCDABCDABCD which is a plausible guess for the original string since we know that the original string was formed by repeating a string of length 4, three times. Here ABCDABCDABCD can be formed by repeating ABCD three times. Here we got a plausible guess by changing only two characters. We cannot do any better.

Sample 2

Here, the original string was a single character repeated five times. AAAAA is a plausible guess for such a string and can be formed by changing only four characters in ABCDE.