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 Main {
	public static int N, K;
	public static String str;
	public static int[] a;

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		N = s.nextInt();
		K = s.nextInt();
		str = s.next();
		a = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			a[i] = str.charAt(i - 1) - 'A' + 1;
		}
		if (K == 2) {
			int[] b = new int[N + 1];
			int[] c = new int[N + 1];
			int res1 = 0;
			int res2 = 0;
			for (int i = 1; i <= N; i++) {
				if (i % 2 == 0) {
					b[i] = 1;
					c[i] = 2;
				} else {
					b[i] = 2;
					c[i] = 1;
				}
				if (a[i] != b[i])
					res1++;
				if (a[i] != c[i])
					res2++;
			}
			if (res1 <= res2) {
				System.out.println(res1);
				StringBuilder sb = new StringBuilder();
				for (int i : b) {
					if (i == 0)
						continue;
					sb.append(toChar(i));
				}
				System.out.println(sb.toString());
			} else {
				System.out.println(res2);
				StringBuilder sb = new StringBuilder();
				for (int i : c) {
					if (i == 0)
						continue;
					sb.append(toChar(i));
				}
				System.out.println(sb.toString());
			}
			return;
		}
		int[][] dp = new int[N + 1][2];
		int[][] last = new int[N + 1][2];
		for (int i = 0; i <= N; i++) {
			for (int k = 0; k < 2; k++) {
				dp[i][k] = 1 << 29;
			}
		}
		dp[0][0] = 0;
		for (int i = 1; i <= N; i++) {
			if (a[i] == a[i - 1]) {
				dp[i][1] = dp[i - 1][0] + 1;
				last[i][1] = 0;
				dp[i][0] = dp[i - 1][1];
				last[i][0] = 1;
			} else {
				if (dp[i - 1][0] <= dp[i - 1][1]) {
					dp[i][0] = dp[i - 1][0];
					last[i][0] = 0;
				} else {
					dp[i][0] = dp[i - 1][1];
					last[i][0] = 1;
				}
				dp[i][1] = dp[i - 1][0] + 1;
				last[i][1] = 0;
			}
		}
		int res = Math.min(dp[N][1], dp[N][0]);
		System.out.println(res);
		int curr = 0;
		if (dp[N][1] < dp[N][0]) {
			curr = 1;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = N; i >= 1; i--) {
			if (curr == 0) {
				sb.append(toChar(a[i]));
			} else {
				sb.append(toChar(getColor(a[i - 1], a[i])));
			}
			curr = last[i][curr];
		}
		sb.reverse();
		System.out.println(sb.toString());
	}

	public static char toChar(int i) {
		return (char) (i + 'A' - 1);
	}

	public static int getColor(int a, int b) {
		for (int i = 1; i <= K; i++) {
			if (i != a && i != b) {
				return i;
			}
		}
		return -1;
	}
}