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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class CF219C {

	static char nextAv(int K, char x) {
		for (int i = 0; i < K; i++)
			if ((char) (i + 'A') != x)
				return (char) (i + 'A');
		return 'A';
	}

	static char nextAv(int K, char x, char y) {
		for (int i = 0; i < K; i++)
			if ((char) (i + 'A') != x && (char) (i + 'A') != y)
				return (char) (i + 'A');
		return 'A';
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int N = sc.nextInt();
		int K = sc.nextInt();
		char[] s = sc.next().toCharArray();
		char[] ans = new char[N];
		for (int i = 0; i < N; i++)
			ans[i] = s[i];
		int i = 0;
		int count = 0;
		if (K == 2) {
			StringBuilder res1 = new StringBuilder();
			StringBuilder res2 = new StringBuilder();
			int diff1 = 0, diff2 = 0;
			for (int k = 0; k < N; k++) {
				res1.append((char) ('A' + (k % 2)));
				res2.append((char) ('A' + ((k + 1) % 2)));
				if (res1.charAt(k) != s[k])
					diff1++;
				if (res2.charAt(k) != s[k])
					diff2++;
			}
			if (diff1 < diff2) {
				System.out.println(diff1);
				System.out.println(res1);
			} else {
				System.out.println(diff2);
				System.out.println(res2);
			}
			return;

		}
		while (i < s.length) {
			int j = i + 1;
			if (j < N && s[i] == s[j]) {
				while (j < N && s[j] == s[i]) {
					j++;
				}
				char put;
				j--;
				if ((j - i + 1) % 2 == 0) {
					if (i != 0 && j + 1 < N) {
						put = nextAv(K, s[i], s[j + 1]);
					} else
						put = nextAv(K, s[i]);
				} else {
					put = nextAv(K, s[i]);
				}
				count += (j - i + 1) / 2;
				int ofst = (i == 0 && (j - i + 1) % 2 == 0 ? 0 : 1);
				for (int k = i + ofst; k <= j; k += 2)
					ans[k] = put;
				i = j;
				continue;
			}
			i++;
		}
		System.out.println(count);
		StringBuilder res = new StringBuilder();
		for (i = 0; i < N; i++)
			res.append(ans[i]);
		System.out.println(res);
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

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

		Scanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(file));
		}

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

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

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

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

	}
}