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

public class CF_219_C_COLOR_STRIPE {

	static int memo[][];
	static int n, k;
	static char[] a;
	static final int INF = (int) 1e9;

	static void print(int iidx, int last) {

		for (int idx = 1; idx < n; idx++) {

			int optimal = memo[idx][last];
			int leave = INF;
			int take = INF;

			if (last != a[idx] - 'A') {
				leave = memo[idx + 1][a[idx] - 'A'];

			}
			if (leave == optimal) {
				st.append((char) (a[idx]));
				last = a[idx] - 'A';

			} else if (last == a[idx] - 'A')
				for (char ch = 'A'; ch < 'A' + k; ch++)
					if (last != ch - 'A') {
						int curr = 1 + memo[idx + 1][ch - 'A'];
						take = Math.min(take, 1 + memo[idx + 1][ch - 'A']);
						if (curr == optimal) {
							st.append((char) (ch));

							last = ch - 'A';
							break;
						}
					}
		}

	}

	static StringBuilder st = new StringBuilder();

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		k = sc.nextInt();

		a = sc.next().toCharArray();

		memo = new int[n + 1][k];

		int ans = INF;

		for (int idx = n - 1; idx >= 0; idx--) {
			for (int last = 0; last < k; last++) {

				int take = INF;
				int leave = INF;

				if (last != a[idx] - 'A')
					leave = memo[idx + 1][a[idx] - 'A'];
				else if (last == a[idx] - 'A')
					for (char ch = 'A'; ch < 'A' + k; ch++) {
						if (last != ch - 'A')
							take = Math.min(take, 1 + memo[idx + 1][ch - 'A']);

					}
				memo[idx][last] = Math.min(take, leave);

			}
		}
		for (int i = 0; i < k; i++) {
			if (ans >= memo[0][i])
				ans = memo[0][i];

		}

		System.out.println(ans);
		for (char ch = 'A'; ch < 'A' + k; ch++) {

			if (ch == a[0]) {
				int curr = memo[1][a[0] - 'A'];
				if (curr == ans) {
					st.append((char) (a[0]));

					print(1, a[0] - 'A');

					break;
				}

			} else if (ch != a[0]) {
				int curr = 1 + memo[1][ch - 'A'];
				if (curr == ans) {
					st.append(ch);

					print(1, ch - 'A');

					break;
				}

			}
		}

		System.out.println(st);

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}