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.LinkedList;
import java.util.List;
import java.util.Scanner;


public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner (System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        String s= sc.nextLine();
        s= sc.nextLine();
        //System.out.println(s);
        //long a=System.currentTimeMillis();
        TaskC c= new TaskC();
        c.solve(n,k,s);
        //System.out.println(String.format("\n%d\n", System.currentTimeMillis()-a));
    }

}
class TaskC{
    int maxm=500005;
    int maxn=26;
    int [] dp_pre = new int[maxn];
    int [] dp_cur = new int[maxn];
    int [][] track=new int[maxm][maxn];
    String letters="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    //if not same dp[i pos-1][X]  = dp[i pos][C]
    //if same, dp[i pos-1][x] = dp[i pos][x+1%k]
    char [] colors= null;//new char[26];


    public void solve(int n,int k,String s){
        colors=letters.toCharArray(); 
        char [] ori = s.toCharArray();
        //init
        for(int i=0;i<k;i++){
            dp_pre[i]=1;
            track[0][i]=i;
        }
        dp_pre[ ori[0]-'A' ]=0;
        track[0][ ori[0]-'A' ] = ori[0]-'A';
        //track[0]
        //xx
        int plus;
        int [] min_array={0,0};
        List<String> sb=new LinkedList<String>();
        for(int i=1;i<n;i++){
            for(int init=0;init<k;init++){
                dp_cur[init]=maxm;
            }
            int cur_min_j=-1;
            int cur_sec_min_j=-1;
            int cur_min=maxm;
            int cur_sec_min=maxm;
            
            if (dp_pre[0]>dp_pre[1]){
                cur_min_j=1;
                cur_sec_min_j=0;
                cur_min=dp_pre[1];
                cur_sec_min=dp_pre[0];
            }else{
                cur_min_j=0;
                cur_sec_min_j=1;
                cur_min=dp_pre[0];
                cur_sec_min=dp_pre[1];
            }
            
            for(int init=2;init<k;init++){
                if(dp_pre[init]<cur_min){
                    cur_min=dp_pre[init];
                    cur_sec_min_j=cur_min_j;
                    cur_min_j=init;
                }else{
                    //dp_pre[init]> min
                    if(dp_pre[init]< cur_sec_min){
                        cur_sec_min_j=init;
                        cur_sec_min=dp_pre[init];
                    }
                    //dp_pre[init]>min and sec_min;
                }
            }
            min_array[0]=cur_min_j;
            min_array[1]=cur_sec_min_j;
            
            //only min and sec_min to update the other.
            //only update  cur +-1;
            // j-> other 26 except j.
            for(int min_j : min_array){
                int cur = ori[i]-'A';
                int left_cur=0;
                left_cur=Math.max(0, cur-2);
                int right_cur=k;
                right_cur=Math.min(k-1,cur+2);
                for( int mm=left_cur;mm<=right_cur;mm++){
                    if(mm!=min_j){
                        plus=0;
                        if(mm!=cur){
                            plus=1;
                        }
                        
                        if(dp_pre[min_j]+plus < dp_cur[mm]){
                            dp_cur[mm]=dp_pre[min_j]+plus;
                            track[i][mm]=min_j;
                        }
    
                    }
                }
            }
            
            for(int init=0;init<k;init++){
                dp_pre[init]=dp_cur[init];
            }
        }
        int min_res=maxm;
        int min_j=-1;
        for(int j=0;j<k;j++){
            if(dp_pre[j]<min_res){
                min_res=dp_pre[j];
                min_j=j;
            }
        
        }
        System.out.println(min_res);
        //System.out.print(String.format("%c", min_j+'A'));
        //char [] res= new char[n];
        StringBuilder xb= new StringBuilder();
        for(int i=n-1;i>=0;i--){
            xb.append((char) (min_j+'A'));
            //res[i]=
            //sb.add(String.format("%c", min_j+'A'));
            min_j=track[i][min_j];
        }
        

        System.out.println(xb.reverse().toString());
        
        
        
        
        
        
        
        
        
    }
}