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 test
{
    
    public static void main(String[] args) throws IOException
    {
        InputStreamReader inp = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(inp);

        String s[] = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int k = Integer.parseInt(s[1]);

        String s1 = br.readLine();
        int paint[] = new int[n+1];
        for(int i=0;i<n;i++)
        {
            int a = s1.charAt(i);
            int b = a-64;
            paint[i+1] = b;
        }

        if(k==2)
        {
            
            int flag1=1;
            int flag2=2;
            int count1=0;
            int count2=0;
            
            for(int i=1;i<=n;i++)
            {
                if(paint[i]==flag1)
                    count2++;
                else
                {
                    count1++;
                }   
        
                flag1=3-flag1;
                flag2=3-flag2;
            }
            int w = Math.min(count1,count2);
            System.out.println(w);
            if(w==count2)
            {
                StringBuilder sb1 = new StringBuilder();
                String z="B";
                String d = "A";
                int y=0;
                for(int i=1;i<=n;i++)
                {
                    
                        if(y==0){
                        sb1.append(z);
                        y=1;}
                        else
                        {
                            sb1.append(d);
                            y=0;
                        }               
                        
                    
                    
                }
                System.out.println(sb1.toString());
            }else
            {
                StringBuilder sb2 = new StringBuilder();
                int y=0;
                String z="A";
                String d = "B";
                for(int i=1;i<=n;i++)
                {
                    
                        if(y==0){
                        sb2.append(z);
                        y=1;}
                        else
                        {
                            sb2.append(d);
                            y=0;
                        }
                    
                    
                }
                System.out.println(sb2.toString());
            }
            return;         
        }

        int cum[] = new int[n+1];
        int prev=0;
        int change=0;
        for(int i=1;i<=n;i++)
        {
            if(paint[i]==prev)
            {
                cum[change]++;
                                
            }else 
            {
                change=i;
                prev = paint[i];
            }
        }
        
        int count=0;
        int i=1;
        while(i<=n)
        {
            if(cum[i]>0)
            {
                if((cum[i]+1)%2==0)
                {
                    
                    int x=0;
                    int max = Math.max(paint[i],paint[i-1]);
                    int min = Math.min(paint[i],paint[i-1]);
                    if(k>max)
                    {
                        x = max+1;
                    }else
                    {
                        if(max-min==1)
                        {
                            x = min-1;
                        }else
                        {
                            x = max-1;
                        }
                    }
                    for(int j=i;j<(i+cum[i]);j=j+2)
                    {
                        paint[j] = x;
                        count++;
                    }
                }else
                {
                    int x=0;
                    if(paint[i]<k)
                    {
                        x = paint[i]+1;
                    }else
                    {
                        x = paint[i]-1;
                    }
                    for(int j=i+1;j<(i+cum[i]);j=j+2)
                    {
                        paint[j] = x;
                        count++;
                    }
                }   
            }
            i = i+cum[i]+1;
        }
        System.out.println(count);
        StringBuilder sb3 = new StringBuilder();
        
        for(int e=1;e<=n;e++)
        {
            char q = (char)(paint[e]+64);
            sb3.append(q);
            
        }
        System.out.println(sb3.toString());
        
    }
}