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
 */
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);
        C219 solver = new C219();
        solver.solve(1, in, out);
        out.close();
    }

    static class C219 {
        int N;
        int K;
        int[] stripe;
        Integer[][] memo;
        char[] alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();

        public int fook(int ind, int nono) {
            int best = N + 2;
            for (int i = 0; i < K; i++) {
                if (i == nono) continue;
                best = Math.min(best, memo[ind][i]);
            }
            return best;
        }

        public int iterativedp() {
            for (int i = N - 1; i >= 0; i--) {
                for (int j = 0; j < K; j++) {
                    if (j == stripe[i]) {
                        memo[i][j] = 1 + fook(i + 1, j);
                    } else {
                        memo[i][j] = memo[i + 1][stripe[i]];
                    }
                }
            }
            int min = N + 2;
            for (int i = 0; i < K; i++)
                min = Math.min(min, memo[0][i]);
            return min;
        }

        public void solve(int testNumber, Scanner s, PrintWriter out) {
            N = s.nextInt();
            K = s.nextInt();
            if (N == 1) {
                out.println(0);
                out.println(s.next());
                return;
            }
            stripe = new int[N];
            char[] spots = s.next().toCharArray();
            for (int i = 0; i < N; i++)
                stripe[i] = spots[i] - 'A';

            memo = new Integer[N + 1][26];
            Arrays.fill(memo[N], 0);
//        memo[N][stripe[N - 1]] = 1;

            int prev = 0;
            while (prev == stripe[0] || prev == stripe[1]) prev++;
            if (K != 26) prev = K;

            int score = iterativedp();
            out.println(score);

//        for(Integer[] row : memo)
//            out.println(Arrays.toString(row));

            for (int i = 0; i < N - 1; i++) {
                // if all future scores are equal, don't change
                int foundlow = -1;
                for (int j = 0; j < K; j++) {
                    if (j == prev) continue;
                    if (memo[i + 1][j] == score - 1) {
                        foundlow = j;
                        score--;
                        break;
                    }
                }
                if (foundlow == -1) {
                    out.print(alp[stripe[i]]);
                    prev = stripe[i];
                } else {
                    out.print(alp[foundlow]);
                    prev = foundlow;
                }
            }
            if (score == 0) out.print(alp[stripe[N - 1]]);
            else {
                for (int i = 0; i < K; i++) {
                    if (i == prev) continue;
                    if (memo[N - 1][i] == 0) {
                        out.print(alp[i]);
                        break;
                    }
                }
            }
            out.println();
        }

    }
}