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

public class Rextester{
    static int findMin(int[][] dp,int i,int j){
        int min = Integer.MAX_VALUE;
        for(int x=0;x<dp[0].length;x++){
            if(x==j){
                continue;
            }
            else{
                min = Math.min(min,dp[i][x]);
            }
        }
        return min;
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        br.close();
        int[][] dp = new int[n][k];
        int min=Integer.MAX_VALUE,min2=Integer.MAX_VALUE,minj=0,minj2=0;
        for(int i=0;i<k;i++){
            if((s.charAt(0)-'A')==i){
                dp[0][i]=0;
                min = 0;
                minj=i;
            }
            else{
                dp[0][i]=1;
                min2 = 1;
                minj2=i;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<k;j++){
                if((s.charAt(i)-'A')==j){
                    if(minj==j){
                        dp[i][j]=min2;
                    }
                    else{
                        dp[i][j]=min;
                    }
                }
                else{
                    if(minj==j){
                        dp[i][j]=min2+1;
                    }
                    else{
                        dp[i][j]=min+1;
                    }
                }
            }
            min=Integer.MAX_VALUE;min2=Integer.MAX_VALUE;minj=0;minj2=0;
            for(int j=0;j<k;j++){
                if(dp[i][j]<=min){
                    min2=min;
                    minj2=minj;
                    min=dp[i][j];
                    minj=j;
                }
                else if(dp[i][j]>min&&dp[i][j]<min2){
                    min2=dp[i][j];
                    minj2=j;
                }
            }
        }
        char[] answer = new char[n];
        int minans = Integer.MAX_VALUE,minansi=0;
        for(int i=0;i<k;i++){
            if(dp[n-1][i]<minans){
                minans=dp[n-1][i];
                minansi=i;
            }
        }
        int ans2 = minans;
        answer[n-1]=(char)(minansi+'A');
        for(int i=n-2;i>=0;i--){
            boolean done = false;
            for(int j=0;j<k;j++){
                if(j==minansi){
                    continue;
                }
                if(dp[i][j]==minans-1){
                    minans--;
                    answer[i]=(char)('A'+j);
                    minansi=j;
                    done=true;
                    break;
                }
            }
            if(done){
                continue;
            }
            for(int j=0;j<k;j++){
                if(j==minansi){
                    continue;
                }
                if(dp[i][j]==minans){
                    answer[i]=(char)('A'+j);
                    minansi=j;
                    done=true;
                    break;
                }
            }
        }
        System.out.println(ans2);
        System.out.println(answer);
    }
}