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

import java.util.*;

public class CF_219_C_COLOR_STRIPE {

	static final int INF = (int) 1e9;

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

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

		char[] a = sc.next().toCharArray();
		int 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++)
			ans = Math.min(ans, memo[0][i]);

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

			if (ch == a[0] && memo[1][a[0] - 'A'] == ans) {

				last = a[0] - 'A';

				break;

			} else if (ch != a[0] && 1 + memo[1][ch - 'A'] == ans) {
				last = ch - 'A';
				break;
			}
		}

		StringBuilder st = new StringBuilder();

		st.append((char) (last + 'A'));

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

			int optimal = memo[idx][last];

			if (last != a[idx] - 'A' && optimal == memo[idx + 1][a[idx] - 'A'])
				st.append((char) ((last = a[idx] - 'A') + 'A'));

			else if (last == a[idx] - 'A')
				for (char ch = 'A'; ch < 'A' + k; ch++)
					if (last != ch - 'A' && 1 + memo[idx + 1][ch - 'A'] == optimal) {
						st.append((char) ((last = ch - 'A') + '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());
		}

	}

}