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

public class ColorStripe{
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st;

    public void run() throws Exception {
        //in = new BufferedReader(new FileReader("D.IN"));
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);

        int n=nextInt();
        int k=nextInt();
        
        String stripe=next();
        char[] chArr= stripe.toCharArray();
        if(k==2)
        {
        	boolean isNowCharA=true;
        	char[][] res=new char[2][];
        	int[] chgCnt=new int[2];
        	for (int i = 0; i < 2; i++) {
				if(i==1) isNowCharA=false;
				res[i]=new char[n];
				for (int j = 0; j < n; j++) {
					if((chArr[j]=='A' && isNowCharA) || (chArr[j]=='B' && !isNowCharA))
					{
						res[i][j]=chArr[j];
					}
					else
					{
						chgCnt[i]++;
						if(chArr[j]=='A') res[i][j]='B';
						if(chArr[j]=='B') res[i][j]='A';
					}						
					isNowCharA=!isNowCharA;
				}
			}
        	char[] toPrint=new char[n];
        	int cnt=-1;
        	if(chgCnt[0]<chgCnt[1]) { toPrint=res[0];cnt=chgCnt[0];}
        	else {toPrint=res[1];cnt=chgCnt[1];}
        	System.out.println(cnt);
        	for (int i = 0; i < n; i++) {
				System.out.print(toPrint[i]);
			}
        	System.out.println();
        	
        }
        else
        {
        	int chgCnt=0;
        	char[] tmp=new char[n];
        	tmp[0]=chArr[0];
        	for (int i = 1; i < n; i++) {
				if(chArr[i]==chArr[i-1])					
				{
					if(i==n-1) tmp[i]=makeDifferent(chArr[i-1], 'C');
					else{tmp[i]=makeDifferent(chArr[i-1], chArr[i+1]); }
					chArr[i]=tmp[i];
					chgCnt++;
				}
				else tmp[i]=chArr[i];
			}
        	System.out.println(chgCnt);
        	for (int i = 0; i < n; i++) {
				System.out.print(chArr[i]);
			}
        	System.out.println();
        }

        out.flush();
        out.close();
        in.close();
    }
    public char makeDifferent(char pre,char next)
    {
    	char[] chMap={'A','B','C'};
    	int[] xx={getCode(pre),getCode(next)};
    	int need=3-xx[0]-xx[1];
    	if(xx[0]==xx[1])  { need=3-xx[0];if (need==3) need=1; }
    	return chMap[need];
    }
    public int getCode(char ch)
    {
    	if(ch=='A') return 0;
    	if(ch=='B') return 1;
    	return 2;
    }

    public static void main(String[] args) throws Exception {
        new ColorStripe().run();
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(in.readLine());
            } catch (Exception e) {
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}