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.*;
public class Problem219C
{
    public static void main (String [] args) 
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        int[] stripe = new int[n+1];
        for(int i=0; i<n; i++) stripe[i+1] = str.charAt(i)-64;
        int[][] dp = new int[n+1][k+1];
        Arrays.fill(dp[1], 1);
        dp[1][stripe[1]] = 0;
        for(int i=2; i<=n; i++)
        {
            int min1 = Integer.MAX_VALUE;
            int min2 = Integer.MAX_VALUE;
            int count1 = 1;
            int count2 = 1;
            for(int j=1; j<=k; j++)
            {
                if(dp[i-1][j]<min1)
                {
                    min2 = min1;
                    count2 = count1;
                    min1 = dp[i-1][j];
                    count1 = 1;
                }
                else if(dp[i-1][j]<min2)
                {
                    min2 = dp[i-1][j];
                    count2 = 1;
                }
                else if(dp[i-1][j]==min1) count1++;
                else if(dp[i-1][j]==min2) count2++;
            }
            for(int j=1; j<=k; j++)
            {
                int append = 1;
                if(j==stripe[i]) append = 0;
                int min = Integer.MAX_VALUE;
                if(dp[i-1][j] == min1)
                {
                    if(count1==1) min = min2;
                    else min = min1;
                }
                else min = min1;
                dp[i][j] = min+append;
            }
        }
        int changes = Integer.MAX_VALUE;
        int color = 0;
        for(int i=1; i<=k; i++) 
        {
            if(dp[n][i]<changes) 
            {
                changes = dp[n][i];
                color = i;
            }
        }
        StringBuilder sb = new StringBuilder();
        int count = n-1;
        sb.append((char) (color+64));
        while(count>0)
        {
            int min = Integer.MAX_VALUE;
            int newcol = 0;
            for(int i=1; i<=k; i++) 
            {
                if(i!=color && dp[count][i]<min)
                {
                    min = dp[count][i];
                    newcol = i;
                }
            }
            color = newcol;
            sb.append((char) (color+64));
            count--;    
        }
        sb.reverse();
        System.out.println(changes);
        System.out.println(sb.toString());
    }
}