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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mthai
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CF_219C solver = new CF_219C();
        solver.solve(1, in, out);
        out.close();
    }

    static class CF_219C {
        public void solve(int testNumber, Scanner input, PrintWriter out) {
            ShortScanner in = new ShortScanner(input);
            int n = in.i(), k = in.i();
            char[] a = (in.s() + '$').toCharArray();

            int ans = 0, l = 0, r = 0;

            if (k == 2) {
                char[] c = new char[a.length], b = new char[a.length];
                Arrays.fill(c, 'A');
                Arrays.fill(b, 'A');
                for (int i = 0; i < n; ++i) {
                    if (i % 2 == 0) b[i] = 'B';
                    else c[i] = 'B';
                }
                int ans1 = 0, ans2 = 0;
                for (int i = 0; i < n; ++i) ans1 += (a[i] != b[i]) ? 1 : 0;
                for (int i = 0; i < n; ++i) ans2 += (a[i] != c[i]) ? 1 : 0;
                if (ans1 < ans2) out.printf("%d\n%s\n", ans1, String.valueOf(b, 0, n));
                if (ans2 <= ans1) out.printf("%d\n%s\n", ans2, String.valueOf(c, 0, n));
                return;
            }

            for (int i = 1; i < a.length; ++i) {
                int len = r - l + 1;
                if (a[i] != a[i - 1]) {
                    ans += len / 2;
                    char x = find(k, a[l], a[i]);
                    if (len % 2 > 0) x = find(k, a[l], a[l]);
                    for (int j = l; j <= r; ++j) {
                        if ((j - l) % 2 > 0) a[j] = x;
                    }
                    l = i;
                }
                r = i;
            }

            out.println(ans);
            for (int i = 0; i < a.length - 1; ++i)
                out.print(a[i]);
            out.println();
        }

        char find(int k, char a, char b) {
            for (int i = 0; i < k; ++i) {
                if ('A' + i != a && 'A' + i != b)
                    return (char) ('A' + i);
            }
            return '$';
        }

        class ShortScanner {
            Scanner in;

            ShortScanner(Scanner in) {
                this.in = in;
            }

            int i() {
                return in.nextInt();
            }

            String s() {
                return in.next();
            }

        }

    }
}