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.*;
import java.io.*;
public class A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String s1[]=br.readLine().split(" ");
            int n=Integer.parseInt(s1[0]);
            int k=Integer.parseInt(s1[1]);
            char c[]=br.readLine().toLowerCase().toCharArray();
            int a[][]=new int[n+1][k];
            int b[][]=new int[n+1][k];
            StringBuffer sb=new StringBuffer();
            
            int min=0,min2=0;
            int u=-1,v=-1;
            for(int i=0;i<n;i++)
            {
                  for(int j=0;j<k;j++)
                  {
                        char d=(char)(j+97);
                        if(d!=c[i])
                         a[i+1][j]=1;
                        if(u==j)
                        { a[i+1][j]+=min2;  b[i+1][j]=v; }
                        else
                        { a[i+1][j]+=min;   b[i+1][j]=u; }
                  }
                  
                  min=n+1;
                  min2=n+1;
                  for(int j=0;j<k;j++)
                   if(min>a[i+1][j])
                   { min=a[i+1][j]; u=j; }
                   
                  for(int j=0;j<k;j++)
                   if(min2>a[i+1][j] && j!=u)
                   { min2=a[i+1][j]; v=j; }
            }
            
      /*      for(int i=0;i<n;i++)
            {
                  for(int j=0;j<k;j++)
                  {
                        System.out.print(a[i+1][j]+" ");
                  }
                  System.out.println();
            }
            
            for(int i=0;i<n;i++)
            {
                  for(int j=0;j<k;j++)
                  {
                        System.out.print(b[i+1][j]+" ");
                  }
                  System.out.println();
            }
            */
            
            int mm=n+1;
            for(int j=0;j<k;j++)
             mm=Math.min(mm,a[n][j]);
            System.out.println(mm);
            
            for(int i=n;i>=1;i--)
            {
                  sb.append((char)(u+65));
                  u=b[i][u];
            }
            sb=sb.reverse();
            System.out.println(sb);
      }
}