Problem: 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.

Input

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.

Output

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

Examples

Input

6 3
ABBACC


Output

2
ABCACA


Input

3 2
BBB


Output

1
BAB

Solution (in JAVA):

Solution:
import java.util.Scanner;

public class problem219C {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();
        int k = reader.nextInt();
        reader.nextLine();
        String inp = reader.nextLine();
        if (n == 1) {
            System.out.println("0");
            System.out.print(inp);
            return;
        }
        if (k == 2) {
            int cntA = 0;
            int cntB = 0;
            StringBuilder ab = new StringBuilder("A");
            StringBuilder ba = new StringBuilder("B");
            boolean flip = true;
            for (int i = 0; i < n; i++) {
                if (inp.charAt(i) == ab.charAt(i)) {
                    cntB++;
                } else {
                    cntA++;
                }
                if (i < n - 1) {
                    if (flip) {
                        ab.append("B");
                        ba.append("A");
                    } else {
                        ab.append("A");
                        ba.append("B");
                    }
                    flip = !flip;
                }
            }
            if (cntA < cntB) {
                System.out.println(cntA);
                System.out.print(ab.toString());
            } else {
                System.out.println(cntB);
                System.out.print(ba.toString());
            }
        } else {
            int count = 0;
            StringBuilder ot = new StringBuilder(inp);
            for (int i = 1; i < n ; i++) {
                if (ot.charAt(i) == ot.charAt(i-1)) {
                    if (i == n-1) {
                        if (ot.charAt(i-1) != 'A') {
                            ot.setCharAt(i, 'A');
                        }
                        else if (ot.charAt(i-1) != 'B') {
                            ot.setCharAt(i, 'B');
                        }
                        else {
                            ot.setCharAt(i, 'C');
                        }
                    } else {
                        if (ot.charAt(i - 1) != 'A'  && ot.charAt(i+1) != 'A') {
                            ot.setCharAt(i, 'A');
                        }
                        else if (ot.charAt(i - 1) != 'B'  && ot.charAt(i+1) != 'B') {
                            ot.setCharAt(i, 'B');
                        }
                        else{
                            ot.setCharAt(i, 'C');
                        }
                    }
                    count++;
                }
            }
            System.out.println(count);
            System.out.print(ot.toString());
        }
    }
}