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.util.Scanner;
public class JavaApplication17 {

    /**
     * @param args the command line arguments
     */
    
    public static void main(String[] args) {
        // TODO code application logic here
        int i,j,change=0;
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int k=input.nextInt();
        String s;
        char[] string=new char[n];
        s=input.next();
        string=s.toCharArray();
        if(k==2){
            char[] r1=new char[n];
            char[] r2=new char[n];
            for(i=0;i<n;i++){
                r1[i]=i%2==0?'A':'B';
                r2[i]=i%2==0?'B':'A';
            }
            int x=findDif(string,r1);
            int y=findDif(string,r2);
            System.out.println(Math.min(x,y));
            System.out.println(x<y?r1:r2);
            return;
        }
        for(i=0;i<string.length;){
            for(j=i+1;j<string.length;j++){
                if(string[j]==string[i])
                    continue;
                else
                    break;
            }
            int len=j-i;
            if(len==1){
                i=j;
                continue;
            }
            if(len%2==0){
                if(j>=string.length){
                    char ch=findAlt(string[i]);
                    for(int l=i+1;l<string.length;l+=2){
                        string[l]=ch;
                        change++;
                    }
                    i=j;
                    break;
                }
                char ch=findAlt(string[i],string[j]);
                for(int l=i+1;l<j;l+=2){
                    string[l]=ch;
                    change++;
                }
            }
            else{
                char ch=findAlt(string[i]);
                for(int l=i+1;l<j;l+=2){
                    string[l]=ch;
                    change++;
                }
            }
            i=j;
        }
        System.out.println(change);
        System.out.println(string);
    }
    static char findAlt(char c1,char c2){
        char aux;
        for(aux='A';aux<='Z';aux++)
            if(aux!=c1 && aux!=c2)
                break;
        return aux;
    }
    static char findAlt(char c1){
        char aux;
        for(aux='A';aux<='Z';aux++)
            if(aux!=c1)
                break;
        return aux;
    }
    static int findDif(char[] samp,char[] tester){
        int res=0;
        for(int i=0;i<samp.length;i++){
            if(samp[i]!=tester[i])
                res++;
        }
        return res;
    }
}