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

/**
 * 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();
    }
}

class TaskC {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int k = in.nextInt();
        char[] s = in.next().toCharArray();
        int len = s.length;
        if (k == 2) {
            int count = 0;
            for (int i = 0; i < len; i++) {
                if ((i & 1) == 0) {
                    if (s[i] == 'A') count++;
                } else {
                    if (s[i] == 'B') count++;
                }
            }
            if (count < (len + 1) / 2) {
                out.println(count);
                for (int i = 0; i < len; i++) {
                    if ((i & 1) == 0) {
                        out.print('B');
                    } else {
                        out.print('A');
                    }
                }
            } else {
                out.println(n - count);
                for (int i = 0; i < len; i++) {
                    if ((i & 1) == 0) {
                        out.print('A');
                    } else {
                        out.print('B');
                    }
                }
            }
            return;
        }
        int count = 1;
        int ans = 0;
        int from = 0;
        int to = 0;
        char[] res = new char[len];
        for (int i = 0; i < len - 1; i++) {
            if (s[i] == s[i + 1]) {
                count++;
                to++;
            } else {
                int color = -1;
                for (int j = 0; j < k; j++) {
                    if (j != (s[from] - 'A') && j != (s[to + 1] - 'A')) {
                        color = j;
                        break;
                    }
                }
                for (int j = from + 1; j <= to; j += 2) {
                    s[j] = (char) (color + 'A');
                    ans++;
                }
                count = 1;
                from = i + 1;
                to = i + 1;
            }
            if (s[i] == s[i + 1] && i + 1 == n - 1) {
                int color = -1;
                for (int j = 0; j < k; j++) {
                    if (j != (s[from] - 'A')) {
                        color = j;
                        break;
                    }
                }
                for (int j = from + 1; j <= to; j += 2) {
                    s[j] = (char) (color + 'A');
                    ans++;
                }
            }
        }
        out.println(ans);
        out.println(new String(s));
    }

}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
        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());
    }

}