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

public class C219 {
    public static void main(String[] args) throws IOException {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s1 = inp.readLine().split(" ");
        int size = Integer.parseInt(s1[0]);
        int b = Integer.parseInt(s1[1]);
        String[] s2 = inp.readLine().split("");
        int[] given  = new int[size];
        ArrayList<Integer> list = new ArrayList<>();
        int count = 1;
        for(int i=0;i<size;i++){
            int a = s2[i].charAt(0);
            given[i] = a;
        }
        for(int i=0;i<size-1;i++){
            int a = s2[i].charAt(0);
            int right = s2[i+1].charAt(0);
            if(a==right){
                count++;
            }
            else{
                if(count>1){
                    list.add(count);
                }
                count = 1;

            }
        }
        if(count>1){
            list.add(count);
        }
        int ans = 0;
        for(int i=0;i<list.size();i++){
            ans+=list.get(i)/2;
        }
        if(given.length==1){
            System.out.println(0);
            System.out.println(s2[0]);
        }
        else if(b>2) {
            int max = 64+b;
            for (int i = 1; i < size-1; i++) {
                if(given[i]==given[i-1]){
                    if(given[i]==max){
                        if(given[i+1]==max-1){
                            given[i]=max-2;
                        }
                        else{
                            given[i]--;
                        }
                    }
                    else if(given[i]==65){
                        if(given[i+1]==66){
                            given[i] = 67;
                        }
                        else{
                            given[i]++;
                        }
                    }
                    else{
                        if(given[i+1]==given[i]+1){
                            given[i]--;
                        }
                        else {
                            given[i]++;
                        }
                    }
                }

            }
            if (given[size - 2] == given[size - 1]) {
                if (given[size - 2] == max) {
                    given[size - 1]--;
                } else if (given[size - 2] == 65) {
                    given[size - 1]++;
                } else {
                    given[size - 1]++;
                }
            }
            System.out.println(ans);
            for(int i=0;i<size;i++){
                char ch = (char) given[i];
                out.write(ch);
            }
            out.flush();
        }
        else{
            int[] check1 = new int[size];
            int[] check2 = new int[size];
            int a = 65;
            int aa = 66;
            for(int i=0;i<size;i++){
                check1[i] = a;
                check2[i] = aa;
                int aaa = a;
                a = aa;
                aa = aaa;
            }
            int diff1 = 0;
            int diff2 = 0;

            for(int i=0;i<size;i++){
                if(given[i]-check1[i]==0){
                    diff1++;
                }
                if(given[i]-check2[i]==0){
                    diff2++;
                }
            }
//            System.out.println(given[0]);
//            System.out.println(diff1+" "+diff2);
            if(diff1>diff2){
                System.out.println(size-diff1);
                for(int i=0;i<size;i++){
                    char ch = (char) check1[i];
                    out.write(ch);
                }
            }
            else {
                System.out.println(size-diff2);
                for(int i=0;i<size;i++){
                    char ch = (char) check2[i];
                    out.write(ch);
                }
            }
            out.flush();
        }

        //System.out.println(list);

    }
}