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:
var nk = readline().split(' ').map(Number);
var n = nk[0];
var k = nk[1];
var s = readline();
if (k == 2){
	var count1 = 0;
	var count2 = 0;
	if (n%2 == 0) {
		var s1 = 'AB'.repeat(n/2);
		var s2 = 'BA'.repeat(n/2);
	} else {
		var s1 = 'AB'.repeat(n/2) + 'A';
		var s2 = 'BA'.repeat(n/2) + 'B';
	}
	for (var i=0; i<n; i++) {
		if (s[i] != s1[i]) count1++;
		else count2++;
	}
	if (count2>count1){
		print(count1);
		print(s1);
	} else {
		print(count2);
		print(s2);
	}
} else {
	s = s.split('');
	var count = 0;
	for (var i=0; i<n-1; i++) {
	if (s[i] == s[i+1]) {
	count++;
	if (i == n-2){
			if (s[i] == 'A') s[i+1] = 'B';
			else s[i+1] = 'A';
		} else {
			if (s[i] != 'A' && s[i+2] != 'A') s[i+1] = 'A';
			if (s[i] != 'B' && s[i+2] != 'B') s[i+1] = 'B';
			if (s[i] != 'C' && s[i+2] != 'C') s[i+1] = 'C';
		}
	}
}
print(count);
print(s.join(''));
}