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.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int k = in.nextInt();
            char[] a = in.next().toCharArray();
            int[][] f = new int[n][k];
            int[][] trace = new int[n][k];
            for (int i = 0; i < k; i++) {
                int current = a[0] - 'A';
                if (i == current) {
                    f[0][i] = 0;
                } else {
                    f[0][i] = 1;
                }
            }
            for (int i = 1; i < n; i++) {
                int current = a[i] - 'A';
                int first = n, second = n;
                int fl = -1, sl = -1;
                for (int j = 0; j < k; j++) {
                    if (f[i - 1][j] <= first) {
                        second = first;
                        sl = fl;
                        first = f[i - 1][j];
                        fl = j;
                    } else if (f[i - 1][j] < second) {
                        second = f[i - 1][j];
                        sl = j;
                    }
                }
                for (int j = 0; j < k; j++) {
                    int best = first;
                    int t = fl;
                    if (j == fl) {
                        best = second;
                        t = sl;
                    }
                    if (j != current) {
                        f[i][j] = best + 1;
                    } else {
                        f[i][j] = best;
                    }
                    trace[i][j] = t;
                }
            }
            int res = n;
            for (int i = 0; i < k; i++) {
                res = Math.min(res, f[n - 1][i]);
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < k; i++) {
                if (f[n - 1][i] == res) {
                    sb.append((char) (i + 'A'));
                    int cur = trace[n - 1][i];
                    for (int j = 2; j <= n; j++) {
                        sb.append((char) (cur + 'A'));
                        cur = trace[n - j][cur];
                    }
                    break;
                }
            }
            out.println(res);
            out.println(sb.reverse().toString());
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}