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.Scanner;


public class ACM {

    
    public static void main(String[] args) {
        Scanner S=new Scanner(System.in);
        String colors;
        int n,k;
        n=S.nextInt();
        k=S.nextInt();
        colors=S.next();
        StringBuilder s=new StringBuilder(colors);
        int counter=0;
        char newchar='A';
        if(k!=2)
        for(int i=1;i<n;i++)
        {
            newchar='A';
            if(s.charAt(i)==s.charAt(i-1))
            {
             //change the color

            
               
                {
                  if(newchar==s.charAt(i-1))
                    newchar++;
                   if(i!=n-1&&newchar==s.charAt(i+1))
                    {newchar++;
                    //check if equels before
                    if(newchar==s.charAt(i-1)&&k!=2)
                      newchar++;
                    }
                }
                
                        
                
                counter++;
                s.setCharAt(i, newchar);
                
            }
            
        }
        else
        if(k==2)
        {
            int counter2=0;
            StringBuilder s2=new StringBuilder(colors); 
            for(int i=0;i<n;i++)
            {
                if(i%2==0)
                {
                    if(s.charAt(i)!='A')
                    { counter++;
                    s.setCharAt(i, 'A');
                    }
                    
                }
                 else
                {
                    if(s.charAt(i)!='B')
                    { counter++;
                    s.setCharAt(i, 'B');
                    }
                    
                }
                
            }
            for(int i=0;i<n;i++)
            {
                if(i%2==1)
                {
                    if(s2.charAt(i)!='A')
                    { counter2++;
                    s2.setCharAt(i, 'A');
                    }
                    
                }
                 else
                {
                    if(s2.charAt(i)!='B')
                    { counter2++;
                    s2.setCharAt(i, 'B');
                    }
                    
                }
                
            }
            if(counter2<counter)
            {counter=counter2;
            s=s2;
            }
            
            
        }
        System.out.println(counter+"\n"+s.toString());
        
        
               
        
        

    }
    
}