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 C {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        char [] s = (in.next()+"1").toCharArray();
        int ans = 0;
        if (k == 2){
            int a = 0;
            int b = 0;
            for (int i = 0; i < n; i++) {
                if ((char)(i%2+65) != s[i]) a++;
                if ((char)((i+1)%2+65) !=s[i]) b++;
            }
            System.out.println(Math.min(a, b));
            int q =1;
            if (b > a){
                q = 0;
            }
            for (int i = 0; i < n; i++) {
                System.out.print((char)((i+q)%2+65));
            }
        }else{
            for (int i = 1; i < n; i++) {
                if (s[i] == s[i-1]){
                    ans++;
                    for (int j = 0; j < k; j++) {
                        if (s[i-1] !=(char)(j+65) && s[i+1]!=(char)(j+65)){
                            s[i] = (char)(j+65);
                            break;
                        }
                    }
                }
            }
            System.out.println(ans);
            for (int i = 0; i < n; i++) {
                System.out.print(s[i]);
            }
        }
    }

}