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

public class CF_219_C_COLOR_STRIPE {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		char[] c = sc.next().toCharArray();

		int ans = 0;
		if (k == 2) {
			char[] ab = new char[n];
			char[] ba = new char[n];
			char ch = 0;
			for (int i = 0; i < n; i++) {
				ab[i] = (char) (ch + 'A');
				ba[i] = (char) ((ch ^ 1) + 'A');
				ch ^= 1;
			}

			int ans1 = 0;
			int ans2 = 0;
			for (int i = 0; i < n; i++)
				if (ab[i] != c[i])
					ans1++;

			for (int i = 0; i < n; i++)
				if (ba[i] != c[i])
					ans2++;

			ans = Math.min(ans1, ans2);
			c = ans1 < ans2 ? ab : ba;

		} else
			for (int i = 1; i < n; i++)
				if (c[i - 1] == c[i])
					for (char ch = 'A'; ch < k + 'A'; ch++)
						if (ch != c[i - 1] && (i == n - 1 || ch != c[i + 1])) {
							ans++;
							c[i] = ch;
							break;
						}

		System.out.println(ans);
		System.out.println(new String(c));

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

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

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

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

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

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

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

	}

}