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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class ColorStripe {

	static int n;
	static int k;
	static char[] s;
	static int[][] par;
	static int[][] dp;

	static int solve(int i, int p) {
		if (i == n)
			return 0;
		if (dp[i][p] != -1)
			return dp[i][p];
		int ans = 99999999;
		if (s[i] - 'A' != p) {
			ans = solve(i + 1, s[i] - 'A');
			par[i][p] = s[i] - 'A';
		}
		for (int j = 0; j < Math.min(4, k); j++)
			if (j != p && 1 + solve(i + 1, j) < ans) {
				ans = 1 + solve(i + 1, j);
				par[i][p] = j;
			}
		return dp[i][p] = ans;
	}

	static void prnt(int i, int p) {
		if (i == n)
			return;
		int req = solve(i, p);
		if (s[i] - 'A' != p && solve(i + 1, s[i] - 'A') == req) {
			out.print(s[i]);
			prnt(i + 1, s[i] - 'A');
			return;
		}
		for (int j = 0; j < k; j++)
			if (j != p && 1 + solve(i + 1, j) == req) {
				out.print((char) ('A' + j));
				prnt(i + 1, j);
				return;
			}
	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		sc = new StringTokenizer("");
		n = nxtInt();
		k = nxtInt();
		s = nxtCharArr();
		dp = new int[n][k];
		par = new int[n][k];
		for (int[] a : dp)
			Arrays.fill(a, -1);
		int minidx = s[0] - 'A';
		int min = solve(1, s[0] - 'A');
		for (int i = 0; i < k; i++) {
			if (1 + solve(1, i) < min) {
				min = 1 + solve(1, i);
				minidx = i;
			}
		}
		out.println(min);
		out.print((char) ('A' + minidx));
		int prev = minidx;
		for (int i = 1; i < n; i++) {
			out.print((char) (par[i][prev] + 'A'));
			prev = par[i][prev];
		}
		out.println();
		br.close();
		out.close();
	}

	static BufferedReader br;
	static StringTokenizer sc;
	static PrintWriter out;

	static String nxtTok() throws IOException {
		while (!sc.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			sc = new StringTokenizer(s.trim());
		}
		return sc.nextToken();
	}

	static int nxtInt() throws IOException {
		return Integer.parseInt(nxtTok());
	}

	static long nxtLng() throws IOException {
		return Long.parseLong(nxtTok());
	}

	static double nxtDbl() throws IOException {
		return Double.parseDouble(nxtTok());
	}

	static int[] nxtIntArr(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtInt();
		return a;
	}

	static long[] nxtLngArr(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nxtLng();
		return a;
	}

	static char[] nxtCharArr() throws IOException {
		return nxtTok().toCharArray();
	}
}