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.*;

public class C219 {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        String s = in.next();
        if (k == 2) {
            int config1 = 0;
            int config2 = 0;
            int choice1 = 0;
            int choice2 = 1;
            for (int i = 0; i < n; i++) {
                int c = s.charAt(i) - 'A';
                if (c != choice1) 
                    ++config1;
                if (c != choice2)
                    ++config2;
                choice1 = (choice1 + 1) % 2;
                choice2 = (choice2 + 1) % 2;
            }
            System.out.println(Math.min(config2, config1));
            if (config1 < config2)
                for (int i = 0; i < n; i++) {
                    if (i % 2 == 0)
                        System.out.print('A');
                    else
                        System.out.print('B');
                }
            else
                for (int i = 0; i < n; i++) {
                    if (i % 2 == 0)
                        System.out.print('B');
                    else
                        System.out.print('A');
                }
        } else {
            char ss[] = s.toCharArray();
            int m = 0;
            for (int i = 1; i < n; i++) {
                if (ss[i] == ss[i - 1]) {
                    ++m;
                    char c = 'A';
                    while (c == ss[i - 1] || (i + 1 < n && c == ss[i + 1]))
                        ++c;
                    ss[i] = c;
                }
            }
            System.out.println(m);
            System.out.println(new String(ss));
        }
    }
}