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 p36{
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args){
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        int[][] dp = new int[n+1][k];
        char[] line = sc.nextLine().toCharArray();
        for(int i=0;i<n;i++)
            arr[i] = (int)(line[i]-'A');


        Arrays.fill(dp[0], 1);
        dp[0][arr[0]] = 0;

        dp[1][arr[0]] = 1;
        for(int i=1;i<n;i++){
            dp[i][0] += (arr[i]==0?0:1);
            int min = dp[i][0];
            for(int j=1;j<k;j++){
                dp[i][j] += (j==arr[i]?0:1);
                dp[i+1][j] = min;
                min = Math.min(min, dp[i][j]);
            }

            min = dp[i][k-1];
            for(int j=k-2;j>=0;j--){
                if(j==0)
                    dp[i+1][j] = min;
                dp[i+1][j] = Math.min(dp[i+1][j], min);
                min = Math.min(min, dp[i][j]);
            }
        }

        // for(int i=0;i<n;i++){
        //     for(int j=0;j<k;j++)
        //         System.out.print(dp[i][j]+" ");
        //     System.out.println(" ");
        // }

        int res = Integer.MAX_VALUE;
        for(int j=0;j<k;j++)
            res = Math.min(res, dp[n-1][j]);

        char[] ans = new char[n];

        int ch = res, prev = -1;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<k;j++)
                if(dp[i][j]==ch && j!=prev){
                    ans[i] = (char)(65+j);
                    ch -= (arr[i]==j?0:1);
                    prev = j;
                    break;
                }
        }


        System.out.println(res);
        System.out.println(String.valueOf(ans));
    }
}