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

public class Main {

	static FastReader input = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);

	static int n, k;
	static char[] a;
	static int[][] memo;
	static char[][] path;
	static boolean[][] visited;

	public static int solve(int indx, int before) {
		if (indx >= n) {
			return 0;
		}

		if (visited[indx][before])
			return memo[indx][before];

		visited[indx][before] = true;

		int min = (int) (1e6);
		char bestChar = a[indx];

		if (a[indx] - 'A' != before) {
			min = memo[indx][before] = solve(indx + 1, a[indx] - 'A');
		}

		for (int i = 0; i < Math.min(3, k); i++) {
			
			int cost = (int) (1e6);

			if (i != before) {
				cost = 1 + solve(indx + 1, i);
			}
			if (cost < min) {
				min = cost;
				bestChar = (char) ('A' + i);
			}
		}
		path[indx][before] = bestChar;
		return memo[indx][before] = min;
	}

	public static void main(String[] args) throws IOException {

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

		a = input.nextLine().toCharArray();

		memo = new int[n + 10][30];
		path = new char[n + 10][30];
		visited = new boolean[n + 10][30];

		out.println(solve(0, 29));

		int before = 29;

		for (int i = 0; i < n; i++) {
			out.print(path[i][before]);
			before = path[i][before] - 'A';
		}

		out.flush();

	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

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

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			String str = "";
			str = br.readLine();
			return str;
		}

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

}