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.*;
import java.math.*;

public class C {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	void solve() throws IOException {
		int n = nextInt(), k = nextInt();
		String s = nextToken();

		int[][] d = new int[n][k];
		char[] alph = new char[k];

		for (int i = 0; i < k; i++)
			alph[i] = (char) ('A' + i);

		for (int i = 0; i < k; i++) {
			if (s.charAt(0) != alph[i])
				d[0][i] = 1;
		}

		for (int i = 1; i < n; i++) {
			int firstInd = 0, secondInd = -1;

			for (int j = 0; j < k; j++) {
				if (d[i - 1][j] < d[i - 1][firstInd])
					firstInd = j;
			}

			for (int j = 0; j < k; j++) {
				if (j != firstInd &&  (secondInd == -1 || d[i - 1][j] < d[i - 1][secondInd]))
					secondInd = j;
			}

			for (int j = 0; j < k; j++) {
				int add = (alph[j] == s.charAt(i)) ? 0 : 1;
				int prev = (j == firstInd) ? d[i - 1][secondInd]
						: d[i - 1][firstInd];

				d[i][j] = prev + add;
			}
		}

		int jp = 0;

		for (int i = 0; i < k; i++)
			if (d[n - 1][i] < d[n - 1][jp])
				jp = i;

		out.println(d[n - 1][jp]);

		restore(n - 1, k, jp, d);

	}

	private void restore(int n, int k, int jp, int[][] d) {

		if (n != 0) {
			int prevInd = -1;

			for (int j = 0; j < k; j++) {
				if (j != jp) {
					if (prevInd == -1 || d[n - 1][j] < d[n - 1][prevInd])
						prevInd = j;
				}
			}

			restore(n - 1, k, prevInd, d);
		}

		char letter = (char) ('A' + jp);

		out.print(letter);
	}

	public static void main(String[] args) {
		new C().run();
	}

	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(42);
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

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

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

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}