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.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
public class ColorStripe {
	public static void main(String[] args) throws IOException {
		OutputStreamWriter streamWriter = new OutputStreamWriter(System.out, "ASCII");
		BufferedWriter out = new BufferedWriter(streamWriter, 512);
		
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		scanner.nextLine();
		String input = scanner.nextLine();
		char[] stripe = new char[n];
		for(int i = 0; i < stripe.length; i++) {
			stripe[i] = input.charAt(i);
		}
		scanner.close();
		if(k > 2) {
			solveManyK(out, n, stripe);
		} else {
			solveTwoK(out, n, stripe);
		}
		out.flush();
	}
	
	private static void solveTwoK(BufferedWriter out, int n, char[] stripe) throws IOException {
		boolean useA = true;
		
		int count1 = 0;
		for(int i = 0; i < n; i++) {
			char target = 'A';
			if(!useA) target = 'B';
			if(stripe[i] != target) count1++;
			useA = !useA;
		}
		useA = false;
		int count2 = 0;
		for(int i = 0; i < n; i++) {
			char target = 'A';
			if(!useA) target = 'B';
			if(stripe[i] != target) count2++;
			useA = !useA;
		}
		
		if(count1 < count2) {
			out.write(count1+"\n");
			useA = true;
			
		} else {
			out.write(count2+"\n");
			useA = false;
		}
		
		for(int i = 0; i < n; i++) {
			if(useA) {
				out.write('A');
			} else {
				out.write('B');
			}
			useA = !useA;
		}
	}
	
	private static void solveManyK(BufferedWriter out, int n, char[] stripe) throws IOException {
		char prev = ' ';
		int run = 0;
		char before = ' ';
		int count = 0;
		for(int i = 0; i < stripe.length; i++) {
			char color = stripe[i];
			if(color != prev) {
				if(run > 1) {
					char toUse = color;
					if(color == before) {
						if(color != 'A' && prev != 'A') {
							toUse = 'A';
						} else if(color != 'B' && prev != 'B') {
							toUse = 'B';
						} else {
							toUse = 'C';
						}
					}
					
					for(int j = i-2; j >= i-run; j-=2) {
						stripe[j] = toUse;
						count++;
					}
				}
				run = 0;
				before = prev;
			}
			prev = color;
			run++;
		}
		if(run > 1) {
			char toUse = 'C';
			if(prev != 'A' && before != 'A') {
				toUse = 'A';
			} else if(prev != 'B' && before != 'B') {
				toUse = 'B';
			}
			
			for(int j = n-2; j >= n-run; j-=2) {
				stripe[j] = toUse;
				count++;
			}
		}
		
		
		out.write(count+"\n");
		for(int i = 0; i < stripe.length; i++) {
			out.write(stripe[i]);
		}
	}
	
}