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.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();
            String s = in.next();
            if (k == 2) {
                int aCount = 0;
                int bCount = 0;
                for (int i = 0; i < n; i++) {
                    if (i % 2 == 0) {
                        if (s.charAt(i) == 'A') bCount++;
                        if (s.charAt(i) == 'B') aCount++;
                    } else {
                        if (s.charAt(i) == 'B') bCount++;
                        if (s.charAt(i) == 'A') aCount++;
                    }
                }
                if (aCount > bCount) {
                    out.println(bCount);
                    for (int i = 0; i < n; i++) {
                        if (i % 2 == 0) out.print('B');
                        else out.print('A');
                    }
                } else {
                    out.println(aCount);
                    for (int i = 0; i < n; i++) {
                        if (i % 2 == 0) out.print('A');
                        else out.print('B');
                    }
                }
            } else {
                char[] ans = s.toCharArray();
                int count = 0;
                for (int i = 1, len = 1; i <= n; i++) {
                    if (i != n && s.charAt(i - 1) == s.charAt(i)) len++;
                    else {
                        if (len % 2 == 0)
                            for (int j = i - len; j < i; j += 2) {
                                for (char c = 'A'; c <= 'Z'; c++) {
                                    if ((j == 0 || c != ans[j - 1]) && c != ans[j + 1]) {
                                        ans[j] = c;
                                        break;
                                    }
                                }
                                count++;
                            }
                        else if (len != 1) {
                            for (int j = i - len + 1; j < i; j += 2) {
                                for (char c = 'A'; c <= 'Z'; c++) {
                                    if (c != ans[j - 1] && c != ans[j + 1]) {
                                        ans[j] = c;
                                        break;
                                    }
                                }
                                count++;
                            }
                        }
                        len = 1;
                    }
                }
                out.println(count);
                for (char c : ans) out.print(c);
            }
        }

    }

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

        public InputReader(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        private void fillTokenizer() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            }
        }

        public String next() {
            fillTokenizer();
            return tokenizer.nextToken();
        }

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

    }
}