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

public class A {

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int k) {
			x = d;
			y = k;
		}

		@Override
		public int compareTo(pair arg0) {
			// TODO Auto-generated method stub
			if (x == arg0.x) {
				return y - arg0.y;
			}
			return x - arg0.x;
		}
	}

	static PrintWriter pw;
	static int n;
	static int m;
	static int k;
	static long[][] memo;
	static long[] cum;
	static char[] a;
	long inf = (long) 1e18;

	static long dp(int idx, int t) {
		if (idx == n)
			return 0;
		if (memo[idx][t] != -1) {
			return memo[idx][t];
		}
		long min = 1000000000;
		for (int i = 0; i < Math.min(k, 3); i++) {
			if (i != t) {
				if (i == a[idx] - 'A')
					min = Math.min(min, dp(idx + 1, a[idx] - 'A'));
				else
					min = Math.min(min, 1 + dp(idx + 1, i));

			}
		}
		if (a[idx] - 'A' != t)
			min = Math.min(min, dp(idx + 1, a[idx] - 'A'));
		return memo[idx][t] = min;
	}

	static void print(int idx, int t, long ans) {
		if (idx == n)
			return;
		for (int i = 0; i < k; i++) {
			if (i != t) {
				if (i == a[idx] - 'A' && dp(idx + 1, i) == ans) {
					pw.print(a[idx]);
					print(idx + 1, i, ans);
					break;

				} else if (dp(idx + 1, i) == ans - 1) {
					pw.print((char) ('A' + i));
					print(idx + 1, i, ans - 1);
					break;
				}
			}
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		a = br.readLine().toCharArray();
		memo = new long[a.length][27];
		for (int i = 0; i < a.length; i++) {
			Arrays.fill(memo[i], -1);
		}
		long ans = dp(0, 26);
		pw.println(ans);
		print(0, 26, ans);
		pw.flush();
		pw.close();

	}

	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

}