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.*;

public class C {
    public static void main(String[] args) throws Exception {
        FastScannerC fs = new FastScannerC();
        PrintWriter out = new PrintWriter(System.out);

        int n = fs.nextInt(), k = fs.nextInt();
        char[] a = fs.nextCharArray();
        if(k == 2) {
            specialCase(a, out);
            out.close();
            return;
        }
        int res = 0;
        for(int i = 0; i < n-1; i++) {
            char now = a[i], next = a[i+1];
            if(now == next) {
                //opt towards changing next first
                boolean[] has = new boolean[k];
                has[a[i]-'A'] = true;
                if(i + 2 < n) has[a[i+2]-'A'] = true;
                int use = -1;
                for(int j = 0; j < k; j++) {
                    if(!has[j]) {
                        use = j;
                        res++;
                        break;
                    }
                }
                if(use >= 0) {
                    a[i+1] = (char)(use + 'A');
                } else {
                    //can't change next so i have to change now.
                    has = new boolean[k];
                    has[a[i+1]-'A'] = true;
                    if(i - 1 >= 0) has[a[i-1]-'A'] = true;
                    use = -1;
                    for(int j = 0; j < k; j++) {
                        if(!has[j]) {
                            use = j;
                            res++;
                            break;
                        }
                    }
                    a[i] = (char)(use+'A');
                }

            }
        }

        out.printf("%d\n", res);
        for(int i = 0; i < n; i++)
            out.printf("%c", a[i]);
        out.printf("\n");
        out.close();
    }

    static void specialCase(char[] a, PrintWriter out) {
        int n = a.length;
        StringBuilder ba = new StringBuilder(), ab = new StringBuilder();
        for(int i = 0; i < n; i++) {
            if(i%2==0) {
                ba.append('B');
                ab.append('A');
            } else {
                ba.append('A');
                ab.append('B');
            }
        }
        int diff1 = 0, diff2 = 0;
        for(int i = 0; i < n; i++) {
            if(a[i] != ba.charAt(i)) diff1++;
            if(a[i] != ab.charAt(i)) diff2++;
        }
        if(diff1 < diff2) {
            out.printf("%d\n%s\n", diff1, ba.toString());
        } else {
            out.printf("%d\n%s\n", diff2, ab.toString());
        }
    }

}



class FastScannerC {
    BufferedReader br;
    StringTokenizer st;

    public FastScannerC() {
        try	{
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        } catch (Exception e){e.printStackTrace();}
    }

    public String next() {
        if (st.hasMoreTokens())	return st.nextToken();
        try {st = new StringTokenizer(br.readLine());}
        catch (Exception e) {e.printStackTrace();}
        return st.nextToken();
    }

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

    public long nextLong() {return Long.parseLong(next());}

    public double nextDouble() {return Double.parseDouble(next());}

    public String nextLine() {
        String line = "";
        try {line = br.readLine();}
        catch (Exception e) {e.printStackTrace();}
        return line;
    }

    public Integer[] nextIntegerArray(int n) {
        Integer[] a = new Integer[n];
        for(int i = 0; i < n; i++) a[i] = nextInt();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = nextInt();
        return a;
    }

    public char[] nextCharArray() {
        return nextLine().toCharArray();
    }
}