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.Scanner;


public class GCD {

	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a = cin.nextInt();
		int b = cin.nextInt();

		if (b == 2) {
			process2(cin.next().toCharArray());
		} else {
			processOther(b, cin.next().toCharArray());
		}
	}

	private static void process2(char[] next) {
		char ch = 'A';
		int cnt1 = 0;
		for (int i = 0; i < next.length; ++i) {
			if (next[i] != ch) {
				++cnt1;
			}
			ch ^= 3;
		}
		ch = 'B';
		int cnt2 = 0;
		for (int i = 0; i < next.length; ++i) {
			if (next[i] != ch) {
				++cnt2;
			}
			ch ^= 3;
		}
		int ans = 0;
		if (cnt1 < cnt2) {
			ans = cnt1;
			ch = 'A';
		} else {
			ans = cnt2;
			ch = 'B';
		}
		for (int i = 0; i < next.length; ++i) {
			next[i] = ch;
			ch ^= 3;
		}
		System.out.println(ans);
		System.out.println(next);
	}

	private static void processOther(int n, char[] next) {
		int cn = 0;
		for (int i = 0; i < next.length; ++i) {
			char a = 0, b = 0;
			if (i != 0) {
				a = next[i - 1];
			}
			if (i + 1 != next.length) {
				b = next[i + 1];
			}
			if (a == next[i]) {
				char ch = 'A';
				if (a == ch || b == ch) {
					++ch;
				}
				if (a == ch || b == ch) {
					++ch;
				}
				next[i] = ch;
				++cn;
			}
		}
		System.out.println(cn);
		System.out.println(next);
	}
}