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.awt.geom.*;
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.regex.*;
import static java.lang.Math.*;

public class Main {
	public Main() throws IOException {
		String input;

		input = br.readLine();
		work(input, 0);

		System.out.print(sb);
	}

	char getDiff(char left, char right, int k) {
		for (int i = (int)'A'; i - (int)'A' < k; i++) {
			char now = (char)i;

			if (now == left) continue;
			if (now == right) continue;
			return now;
		}

		return right;
	}

	private void work(String input, int t) throws IOException {
		//debug(t, input);
		String[] inputArray = input.split(" ");
		int n = Integer.valueOf(inputArray[0]);
		int k = Integer.valueOf(inputArray[1]);
		char[] retStr = new char[n];
		char[] retBA = new char[n];
		int ret = 0;

		input = br.readLine();

		if (k == 2) {
			for (int i = 0; i < n;i ++) {
				if ((i % 2) == 0) {
					retStr[i] = 'A';
					retBA[i] = 'B';
				} else {
					retStr[i] = 'B';
					retBA[i] = 'A';
				}

				if (input.charAt(i) != retStr[i])
					ret++;
			}

			if (ret > (input.length() / 2)) {
				ret = input.length() - ret;
				retStr = retBA;
			}

			sb.append(ret);
			sb.append('\n');
			sb.append(retStr);
			return;
		}

		retStr[0] = input.charAt(0);
		for (int i = 1; i < n; i++) {
			char now = input.charAt(i);
			char left = retStr[i - 1];
			char right;

			if (now != left) {
				retStr[i] = now;
				continue;
			}

			if (i + 1 == n)
				right = left;
			else
				right = input.charAt(i + 1);

			ret++;
			retStr[i] = getDiff(left, right, k);
		}

		sb.append(ret);
		sb.append('\n');
		sb.append(retStr);
	}

	StringBuilder sb = new StringBuilder();
	BufferedReader br = new BufferedReader(
		new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
			new Main();
	}

	public static void debug(Object... arr) {
		System.err.println(Arrays.deepToString(arr));
	}
}