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.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.*;

public class C implements Runnable{
	
	final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	
	BufferedReader in;
	PrintWriter out;
	StringTokenizer tok = new StringTokenizer("");
	
	void init() throws FileNotFoundException{
		if (ONLINE_JUDGE){
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
		}else{
			in = new BufferedReader(new FileReader("input.txt"));
			out = new PrintWriter("output.txt");
		}
	}
	
	String readString() throws IOException{
		while(!tok.hasMoreTokens()){
			try{
				tok = new StringTokenizer(in.readLine());
			}catch (Exception e){
				return null;
			}
		}
		return tok.nextToken();
	}
	
	int readInt() throws IOException{
		return Integer.parseInt(readString());
	}
	
	long readLong() throws IOException{
		return Long.parseLong(readString());
	}
	
	double readDouble() throws IOException{
		return Double.parseDouble(readString());
	}
	
	public static void main(String[] args){
		new Thread(null, new C(), "", 200 * (1L << 20)).start();
	}
	
	long timeBegin, timeEnd;

	void time(){
		timeEnd = System.currentTimeMillis();
		System.err.println("Time = " + (timeEnd - timeBegin));
	}
	
	long memoryTotal, memoryFree;
	

	void memory(){
		memoryFree = Runtime.getRuntime().freeMemory();
		System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10) + " KB");
	}
	
	void debug(Object... objects){
		if (DEBUG){
			for (Object o: objects){
				System.err.println(o.toString());
			}
		}
	}
	
	public void run(){
		try{
			timeBegin = System.currentTimeMillis();
			memoryTotal = Runtime.getRuntime().freeMemory();
			init();
			solve();
			out.close();
			time();
			memory();
		}catch (Exception e){
			e.printStackTrace(System.err);
			System.exit(-1);
		}
	}
	
	boolean DEBUG = false;
	
	void solve() throws IOException{
		int n = readInt();
		int k = readInt();
		
		char[] c = in.readLine().toCharArray();
		
		int[][] dp = new int[n][k];
		Arrays.fill(dp[0], 1);
		dp[0][c[0]-'A'] = 0;
		
		int[][] p = new int[n][k];
		
		for (int i = 1; i < n; ++i){
			int min_k = -1;
			for (int j = 0; j < k; ++j){
				if ((min_k == -1 || dp[i-1][min_k] > dp[i-1][j])){
					min_k = j;
				}
			}
			
			for (int j = 0; j < k; ++j){
				if (j == min_k) continue;
				dp[i][j] = dp[i-1][min_k] + (j == c[i] - 'A'? 0: 1);
				p[i][j] = min_k;
			}
			
			int value = min_k;
			min_k = -1;
			for (int j = 0; j < k; ++j){
				if (j != value && (min_k == -1 || dp[i-1][min_k] > dp[i-1][j])){
					min_k = j;
				}
			}
			p[i][value] = min_k;
			
			dp[i][value] = dp[i-1][min_k] + (value == c[i] - 'A'? 0: 1);
		}
		
		int min_k = -1;
		for (int j = 0; j < k; ++j){
			if ((min_k == -1 || dp[n-1][min_k] > dp[n-1][j])){
				min_k = j;
			}
		}
		
		out.println(dp[n-1][min_k]);
		
		List<Character> list = new ArrayList<Character>();
		for (int i = n - 1; i >= 0; --i){
			list.add((char) (min_k + 'A'));
			
			min_k = p[i][min_k];
		}
		
		Collections.reverse(list);
		for (char ch: list){
			out.print(ch);
		}
	}
}