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.*;
import java.io.*;

public class Round135Div2C2 {
	public static void main(String[] args) throws IOException 
	{
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		st = new StringTokenizer(rd.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		S = rd.readLine();
		if(k==2){
			char[] A = new char[n];
			for(int i=0; i<n; i++) A[i] = (i%2==0? 'A': 'B');
			char [] B = new char[n];
			for(int i=0; i<n; i++) B[i] = (i%2==1? 'A': 'B');
			int fir = dist(new String(A), S), sec = dist(new String(B), S);
			pw.println(Math.min(fir, sec));
			if(fir<=sec){
				pw.println(new String(A));
			}
			else pw.print(new String(B));
			pw.flush();
			return;
		}
		int[][] d = new int[n][k];
		for(int i=0; i<k; i++){
			d[0][i] = (S.charAt(0)==(char)('A'+i))? 0: 1;
		}
		for(int i=1; i<n; i++){
			for(int j=0; j<k; j++){ // find d[i][j] 
				int ch = (int) (S.charAt(i)-'A');
				int min = n;
				for(int t=0; t<k; t++){
					if(t==j) continue;
					int cur = d[i-1][t];
					if(ch!=j) cur++;
					min = Math.min(min, cur);
				}
				d[i][j] = min;
			}
		}
		int min = n+1, ans = 0;
		for(int i=0; i<k; i++){
			if(min>d[n-1][i]){
				min = d[n-1][i];
				ans = i;
			}
		}
		char[] res = new char[n];
		res[n-1] = (char) ('A'+ans);
		int last = ans;
		for(int i=n-2; i>=0; i--){
			for(int j=0; j<k; j++){
				if(j==last) continue;
				int cur = d[i][j];
				if(last!=(int)(S.charAt(i+1)-'A')) cur++;
				if(cur==d[i+1][last]){
					res[i] = (char) ('A'+j);
					last = j;
					break;
				}
			}
		}
		pw.println(min);
		pw.println(new String(res));
		pw.flush();
	}
	
	
	
	
	static int dist(String a, String b){
		int x = 0;
		for(int i=0; i<a.length(); i++) if(a.charAt(i)!=b.charAt(i)) x++;
		return x;
	}
	
	static String S;
	static int n, k;
	
	static StringTokenizer st;
	
}