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.*;
import java.util.StringTokenizer;

public class Cbr {

    public static void main(String[] args) throws IOException {
        Cbr cbr = new Cbr();
        cbr.run();
        cbr.out.flush();
    }

    private void run() throws IOException {
        int n = nextInt(), k = nextInt();
        String s = nextToken();
        if (k == 2) {
            int ca, cb;
            ca = cb = 0;
            for (int i = 0; i < n; i++) {
                if ((i & 1) == 0) {
                    if (s.charAt(i) != 'A') ca++;
                    if (s.charAt(i) != 'B') cb++;
                } else {
                    if (s.charAt(i) != 'B') ca++;
                    if (s.charAt(i) != 'A') cb++;
                }
            }
            out.println(Math.min(ca, cb));
            if (ca < cb) {
                for (int i = 0; i < n; i++)
                    out.print((i & 1) == 0 ? 'A' : 'B');
            } else {
                for (int i = 0; i < n; i++)
                    out.print((i & 1) == 1 ? 'A' : 'B');
            }
            return;
        }
        int count = 0;
        int j = 0;
        StringBuilder sb = new StringBuilder(s.length());
        while (j < n) {
            int i = j++;
            while (j < n && s.charAt(i) == s.charAt(j))
                j++;
            count += (j - i) / 2;
            char c;
            for (c = 'A'; c < k + 'A'; c++)
                if (c != s.charAt(i) && (j >= n || c != s.charAt(j)))
                    break;
            for (int q = i; q < j; q += 2) {
                sb.append(s.charAt(q));
                if (q + 1 != j)
                    sb.append(c);
            }
        }
        out.println(count);
        out.println(sb);
    }

    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private PrintWriter out = new PrintWriter(System.out);

    private StringTokenizer st;

    private String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

}