CF219C.Color Stripe

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.

一条彩色条纹由一行 $n$ 个正方形格子组成，每个格子被涂上 $k$ 种颜色中的一种。你的任务是重绘最少数量的格子，使得任意两个相邻格子的颜色均不相同。重绘时，你可以使用编号为 $1$ 到 $k$ 的任意一种颜色。

The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 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.

第一行输入包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 5·10^5$；$2 ≤ k ≤ 26$）。第二行包含 $n$ 个大写英文字母。“A” 表示第一种颜色，“B” 表示第二种颜色，依此类推。仅可能使用前 $k$ 个英文字母。每个字母表示条带中对应格子的颜色。

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

输出一个整数——所需的最少重涂次数。第二行输出任意一种可能的重涂后的条纹方案。