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

public class C {
    static int n;
    static int k;
    static int[][] DP;
    static int[][] N;
    static int inf = (int) 1e9;
    static int[] A;

    public static int get(int index, int last) {
        if (index == n)
            return 0;
        if (DP[index][last] != -1)
            return DP[index][last];
        int same = inf;
        if (A[index] != last)
            same = get(index + 1, A[index]);
        int front = inf;
        if (index < n - 1 && A[index + 1] != last)
            front = 1 + get(index + 1, A[index + 1]);
        int diff = inf;
        int col = 1;
        if (last == 1 || (index < n - 1 && A[index + 1] == 1)) {
            col = 2;
            if (last == 2 || (index < n - 1 && A[index + 1] == 2))
                col = 3;
        }
        if (col <= k)
            diff = 1 + get(index + 1, col);
        if (same <= front && same <= diff) {
            N[index][last] = A[index];
            return DP[index][last] = same;
        } else if (diff <= front && diff <= same) {
            N[index][last] = col;
            return DP[index][last] = diff;
        } else {
            N[index][last] = A[index + 1];
            return DP[index][last] = front;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] S = in.readLine().split(" ");
        n = Integer.parseInt(S[0]);
        k = Integer.parseInt(S[1]);
        String s = in.readLine();
        A = new int[n];
        for (int i = 0; i < s.length(); i++)
            A[i] = s.charAt(i) - 'A' + 1;
        DP = new int[n][k + 1];
        N = new int[n][k + 1];
        for (int i = 0; i < n; i++)
            Arrays.fill(DP[i], -1);
        for (int i = n - 1; i >= 0; i -= 100)
            for (int j = 1; j <= k; j++)
                get(i, j);
        int ans = get(0, 0);
        System.out.println(ans);
        char[] res = new char[n];
        int last = 0;
        for (int i = 0; i < n; i++) {
            res[i] = (char) (N[i][last] + 'A' - 1);
            last = N[i][last];
        }
        System.out.println(new String(res));
    }
}