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 C {
	
	int n, k;
	int[] s;
	int[][] f;
	
	public void solve() throws IOException {
		n = nextInt();
		k = nextInt();
		
		String tmp = nextToken();
		s = new int[n];
		for (int i = 0; i < n; i++) s[i] = tmp.charAt(i) - 'A';
		
		if (k < 4) {
			DP();
			return;
		}
		
		int last = 0;
		int ans = 0;
		for (int i = 1; i < n; i++)
			if (s[i] != s[i - 1]) {
				boolean[] already = new boolean[k];
				if (last > 0) {
					already[s[last - 1]] = true;
				}
				already[s[i]] = true;
				already[s[last]] = true;
				int newColor = -1;
				for (int j = 0; j < 26; j++)
					if (!already[j]) {
						newColor = j;
						break;
					}
				for (int j = last + 1; j < i; j += 2) {
					ans++;
					s[j] = newColor;
				}
				last = i;
			}
		boolean[] already = new boolean[k];
		if (last > 0) already[s[last - 1]] = true;
		already[s[last]] = true;
		int newColor = -1;
		for (int j = 0; j < 26; j++)
			if (!already[j]) {
				newColor = j;
				break;
			}
		for (int j = last + 1; j < n; j += 2) {
			ans++;
			s[j] = newColor;
		}
		writer.println(ans);
		for (int i = 0; i < n; i++)
			writer.print((char)(s[i] + 'A'));
	}
	
	void DP() {
		f = new int[n][k];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < k; j++) f[i][j] = 1000000000;
		for (int j = 0; j < k; j++)
			if (j == s[0]) f[0][j] = 0;
			else f[0][j] = 1;
		for (int i = 0; i < n - 1; i++)
			for (int j = 0; j < k; j++)
				if (f[i][j] != 1000000000)
					for (int jj = 0; jj < k; jj++) {
						if (jj == j) continue;
						int add = 0;
						if (jj != s[i + 1]) add++;
						f[i + 1][jj] = Math.min(f[i + 1][jj], f[i][j] + add);
					}
		int ans = 1000000000;
		int where = -1;
		for (int j = 0; j < k; j++)
			if (ans > f[n - 1][j]) {
				ans = f[n - 1][j];
				where = j;
			}
		writer.println(ans);
		trace(n - 1, where);
		writer.println();
	}
	
	void trace(int i, int j) {
		if (i == 0) {
			writer.print((char)(j + 'A'));
			return;
		}
		int add = 0;
		if (j != s[i]) add++;
		for (int jj = 0; jj < k; jj++) {
			if (jj == j) continue;
			if (f[i - 1][jj] != 1000000000 && f[i - 1][jj] + add == f[i][j]) {
				trace(i - 1, jj);
				break;
			}
		}
		writer.print((char)(j + 'A'));
	}

	public static void main(String[] args) throws FileNotFoundException {
		new C().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() {
		try {
			long tbegin = System.currentTimeMillis();
			reader = new BufferedReader(new InputStreamReader(System.in));
			//reader = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			//writer = new PrintWriter(new FileOutputStream("output.txt"));
			solve();
			//reader.close();
			//System.out.println(System.currentTimeMillis() - tbegin + "ms");
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

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

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

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

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

}