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

public class Main {
	
	public static void main(String[] args) {
		PrintWriter out = new PrintWriter(System.out, true);
		Scanner in = new Scanner(System.in);
		Main solver = new Main(in, out);
		solver.run();
	}

	Scanner     in;
	PrintWriter out;

	public Main(Scanner i, PrintWriter o) {
		in  = i;
		out = o;
	}
	
	char next(char c) {
		char m = (char)('A' + k -1);
		if (c == m) {
			return 'A';
		}
		c = (char)(c + 1);
		return c;
	}
	
	int diff(char[] a, char[] b) {
		int n = a.length;
		int r = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] != b[i]) r++;
		}
		return r;
	}
	
	int n, k;
	
	public void run() {		
		n = in.nextInt();
		k = in.nextInt();
		char[] s = in.next().toCharArray();
		if (n == 1) {
			out.println(0);
			out.println(s);
			return;
		}
		int i;
		int ans = 0;
		char[] res = null;
		if (k == 2) {
			char[] s1 = s.clone();
			for (i = 0; i < n; i += 2) s1[i] = 'A';
			for (i = 1; i < n; i += 2) s1[i] = 'B';
			ans = diff(s1, s);
			res = s1;
			char[] s2 = s.clone();
			for (i = 0; i < n; i += 2) s2[i] = 'B';
			for (i = 1; i < n; i += 2) s2[i] = 'A';
			int d = diff(s2, s);
			if (d < ans) {
				ans = d;
				res = s2;
			}
		}
		else { // k > 2
			i = 0;
			int j, k;
			while (i < n) {
				j = i;
				while (j+1 < n && s[j+1] == s[i]) j++;
				if (j > i) {
					char c = (j+1 < n ? s[j+1] : ' ');
					char a = s[i];
					while (a == s[i] || a == c) a = next(a);
					for (k = i+1; k <= j; k += 2) {
						s[k] = a;
					}
					ans += (j-i+1)/2;
				}
				i = j+1;
			}
			res = s;
		}		
		out.println(ans);
		out.println(res);
		return;
	}	
}