彩色条纹由水平行的 n 个方形单元表示,每个单元都涂有 k 种颜色之一。您的任务是重新绘制最少数量的单元格,以便没有两个相邻单元格具有相同的颜色。您可以使用 1 到 k 之间的任何颜色来重新绘制单元格。
输入
第一个输入行包含两个整数 n 和 k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26)。第二行包含n个大写英文字母。字母“A”代表第一种颜色,字母“B”代表第二种颜色,依此类推。可以使用前k个英文字母。每个字母代表条纹相应单元格的颜色。
输出
打印一个整数——所需的最小重画次数。在第二行中打印重新绘制的条纹的任何可能的变体。
示例
输入 #1
6 3 ABBACC
输出 #1
2 ABCACA
输入 #2
3 2 BBB
输出 #2
1 BAB