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:
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int n,k;
		Scanner sc = new Scanner(System.in);
		n =sc.nextInt();
		k = sc.nextInt();
		String s = sc.next();
		
		char[] charArray = s.toCharArray();
		int count=0;
		
		if(k==2){
		    int distanceFromA =0;
		    char[] charWithAStart = new char[charArray.length];
		    for(int i=0; i < charArray.length; i++){
		        if(i%2 == 0){
		            charWithAStart[i] = 'A';
		        }
		        else{
		            charWithAStart[i] = 'B';
		        }
		        distanceFromA += Math.abs((int)charWithAStart[i] - (int)charArray[i] );
		    }
		    char[] charWithBStart = new char[charArray.length];
		    int distanceFromB =0;
		    
		    for(int i=0; i < charArray.length; i++){
		        if(i%2 == 0){
		            charWithBStart[i] = 'B';
		        }
		        else{
		            charWithBStart[i] = 'A';
		        }
		        distanceFromB += Math.abs((int)charWithBStart[i] - (int)charArray[i] );
		        
		    }
		    
		    if(distanceFromA > distanceFromB){
		        System.out.println(distanceFromB);
		        System.out.println(new String(charWithBStart));
            }
            else{
                System.out.println(distanceFromA);
                System.out.println(new String(charWithAStart));

            }
		    return;
		}
		
		for(int i=1; i < charArray.length; i++){
		    if(charArray[i-1] == charArray[i]){
		        count++;
		        
		        if(i+1 < charArray.length){
		          //  System.out.println("i: " + i + " " + charArray[i]);
		            charArray[i] = findMostSuitableChar(charArray[i],charArray[i+1],k);
		        }
		        else{
		          //  System.out.println("i: " + i + " " + charArray[i]);
		            charArray[i] = findMostSuitableChar(charArray[i],null,k);
		        }
		    }
		}
		System.out.println(count);
		System.out.println(new String(charArray));
	}
	
	public static Character findMostSuitableChar(Character cur, Character next,int k){
	    if(next == null){
	        for(int k1=0; k1 <k; k1++){
	            Character temp = (char)((int)'A' + k1);
	            if(temp!= cur){
	                return temp;
	            }
	        }
	        return null;
	        
	    }else{
	        for(int k1=0; k1 <k; k1++){
	           // System.out.println("temp: ");
	            Character temp = (char)((int)'A' + k1);
	            if(temp!= cur && temp!= next){
	               // System.out.println("temp: "+ temp);
	                return temp;
	            }
	        }
	       
	       return null;
	    }
	}
}