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.util.*;
import java.lang.*;
import java.io.*;

public class CO_219C {
	static int imax = Integer.MAX_VALUE, imin = Integer.MIN_VALUE;
	static long lmax = Long.MAX_VALUE, lmin = Long.MIN_VALUE;
	static long mod = (long) 1e9 + 7;

	public static void main(String[] args) throws java.lang.Exception {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		// int test=in.ni();
		int test = 1;
		while (test-- > 0) {
			int n = in.ni();
			int k = in.ni();
			char str[] = in.ncs();
			if (k == 2) {
				int cnt = 0;
				char tmp[] = new char[n];
				for (int i = 0; i < n; i++) {
					tmp[i] = str[i];
				}
				for (int i = 1; i < n; i++) {
					if (tmp[i] == tmp[i - 1]) {
						tmp[i] = tmp[i] == 'A' ? 'B' : 'A';
						cnt++;
					}
				}
				int min = cnt;
				for (int i = 0; i < n; i++) {
					tmp[i] = str[i];
				}
				tmp[0] = tmp[0] == 'A' ? 'B' : 'A';
				cnt = 1;
				for (int i = 1; i < n; i++) {
					if (tmp[i] == tmp[i - 1]) {
						tmp[i] = tmp[i] == 'A' ? 'B' : 'A';
						cnt++;
					}
				}
				// System.out.println("cnt " + cnt);
				if (cnt < min) {
					System.out.println(cnt);
					System.out.println(new String(tmp));
				} else {
					// System.out.println(min + " first");
					for (int i = 0; i < n; i++) {
						tmp[i] = str[i];
					}
					for (int i = 1; i < n; i++) {
						if (tmp[i] == tmp[i - 1]) {
							tmp[i] = tmp[i] == 'A' ? 'B' : 'A';
							cnt++;
						}
					}
					System.out.println(min + "\n" + new String(tmp));
				}
			} else {
				TreeSet<Character> set = new TreeSet();
				char a = 'A';
				char b = 'B';
				char c = 'C';
				set.add(a);
				set.add(b);
				set.add(c);
				int cnt = 0;
				for (int i = 0; i + 1 < n; i++) {
					if (str[i] == str[i + 1]) {
						cnt++;
						if (a == str[i] || i + 2 < n && a == str[i + 2]) {
							set.remove(a);
						}
						if (b == str[i] || i + 2 < n && b == str[i + 2]) {
							set.remove(b);
						}
						if (c == str[i] || i + 2 < n && c == str[i + 2]) {
							set.remove(c);
						}
						str[i + 1] = set.pollFirst();
						set.add(a);
						set.add(b);
						set.add(c);
					}
				}
				System.out.println(cnt + "\n" + new String(str));
			}
		}
		out.close();
	}

	static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

	}

	static void print(int arr[], int len) {
		for (int i = 0; i < len; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	static class InputReader {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int ni() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c & 15;
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c & 15;
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String ns() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public char[] ncs() {
			return ns().toCharArray();
		}

		public String nLine() {
			int c = read();
			// while (c != '\n' && c != '\r' && c != '\t' && c != -1)
			// c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (c != '\n' && c != '\r' && c != '\t' && c != -1);
			return res.toString();
		}

		public static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

	}

}