Color Stripe

题意翻译

给出一个字符串，只包含k种字符，问最少修改多少个字符（不增长新的种类）能够得到一个新的字符串，这个字符串满足相邻的字符没有相同的。

题目描述

A colored stripe is represented by a horizontal row of $ n $ square cells, each cell is pained one of $ k $ colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to $ k $ to repaint the cells.

输入输出格式

输入格式

The first input line contains two integers $ n $ and $ k $ ( $ 1<=n<=5·10^{5}; 2<=k<=26 $ ). The second line contains $ n $ uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first $ k $ English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

输出格式

Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

输入输出样例

输入样例 #1

6 3
ABBACC

输出样例 #1

2
ABCACA

输入样例 #2

3 2
BBB

输出样例 #2

1
BAB