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.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

/*************************************************************************
 *  219D Codeforce
 * 
 *************************************************************************/
public class Sourcecode {
    public static class Record{
        public int min;
        public short from;
    
    }
    
    public static void main (String[] args) {
        
       Scanner scan=new Scanner(System.in);
       int N = scan.nextInt();
       int K = scan.nextInt();
       int[] forward = null,backward = null;
       if (K==2){
           forward=new int[N+1];
           backward=new int[N+1];
           for(int i=1;i<=N;i++){
               if(i%2!=0){ forward[i]=1;backward[i]=2;}
               else { forward[i]=2;backward[i]=1;}
           }
           
       }
       String input = scan.next();
       int[] inputint=new int[N+1];
       for(int i=1;i<=N;i++){
           inputint[i]=input.charAt(i-1)-'A'+1;
       }
       if(K==2){
        int diffforward=diff(inputint,forward);
        int diffback=diff(inputint,backward);
        if(diffforward<diffback){
            System.out.println(diffforward);
            printit(forward);
        }
        else{
            System.out.println(diffback);
            printit(backward);
        }
         return;  
       }
       int allcount=0;
       for(int i=1;i<=N-1;){
           int t=i;
           int count=1;
           while(t+1<=N&&inputint[t]==inputint[t+1]){
               count++;
               t++;
           }
           t++;
          
           
               int nextafter;
               if(t<=N){
               nextafter=inputint[t];
               }
               else{
                nextafter=inputint[t-1];
               }
               int j = 0;
               if(count%2==0){
               j=t-1;}
               else{j=t-2;}
               while(j>i){
                   int tmp=inputint[j];
                   int m;
                   for(m=1;m<=K;m++){
                       
                       if(count%2==0&&m!=tmp&&m!=nextafter) break;
                       if(count%2!=0&&m!=tmp) break;
                   }
                   if(m<K+1) inputint[j]=m;
                   j-=2;
               }
               
           
           allcount+=(count/2);
           i=t;
       }
       System.out.println(allcount);
       printit(inputint);
    }

    private static int diff(int[] inputint, int[] other) {
        int diff=0;
        for(int i=1;i<inputint.length;i++){
            if(inputint[i]!=other[i]) diff++;
        }
        return diff;
    }

    private static void printit(int[] inputint) {
        for(int m=1;m<inputint.length;m++){
            int i=inputint[m];
            int intshow = 'A' + i - 1;
            char show = (char) intshow;
            System.out.print(show);
        }
        
    }
    }