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




/**
 *
 * @author ehab
 */

public class JavaApplication7 {
 static int k ; static int dp [] [] = new int[500001][27] ;
 static int ar [] , r[];
 
  static int rec(int m  , int i)
{ 
 if(m == k)
     return 0 ;
 int h = 9999999 ;
 if(dp[m][i] != -1)
     return dp [m][i] ;
 if(r[m] == ar[i])
 for(int j = 0 ; j < ar.length ; j++)
     if(ar[i] == ar[j])
         continue;
     else
         h = Math.min( rec(m + 1,j) + 1, h) ;
else
   return  dp[m][i] = rec(m + 1 , r[m]) ;
 return dp[m][i] = h ;
}
static void re2(int m  , int i){

if(m == k)
     return  ;
 int h = 9999999 ;
int ind = 0 ;
 if(r[m] == ar[i])
 for(int j = 0 ; j < ar.length ; j++)
     if(ar[i] == ar[j])
         continue;
     else
     { int x =  rec(m + 1,j) + 1 ; if(h > x ) {h = x ;ind = j;} }
else
 {ans.append((char)(r[m]+'A'));  re2(m + 1 , r[m]) ; return ;}
 {ans.append((char)(ind+'A')) ;  re2(m+1,ind) ; }  
}
    static StringBuilder ans = new StringBuilder() ;
    public static void main(String[] args) throws Exception 
    {
      
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)) ;
        StringTokenizer st = new StringTokenizer(bf.readLine()) ;
        k = Integer.parseInt(st.nextToken()) ; 
        int n = Integer.parseInt(st.nextToken()) ;  
        ar = new int[n] ;
        for(int i = 0 ; i < n ; i++) 
         ar[i] = i  ;
        for(int i = 0 ; i < dp.length ; i++)
            Arrays.fill(dp[i], -1);
        StringBuilder t = new StringBuilder(bf.readLine()) ;
        r  = new int [k] ;
        for(int i = 0 ; i < k ;i++)
            r[i] = t.charAt(i) - 'A' ;
        
        int m = rec(1,r[0])   ;
        
        for(int i = 0 ; i < dp.length ; i++)
            Arrays.fill(dp[i], -1);
        int w = rec(0,r[0]);
         for(int i = 0 ; i < dp.length ; i++)
            Arrays.fill(dp[i], -1);
        if(m < w )
        { System.out.println(m); re2(1,r[0]) ; System.out.println((char)(r[0]+'A')+""+ ans);}
        else {System.out.println(w);re2(0,r[0]) ; System.out.println(ans);}
        
    } 
    }