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.*;
 
public class File {
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				}
				catch (IOException e) {
					e.printStackTrace();
				}
			}
			
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		
		
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		int changes = 0;
		char[] str = sc.next().toCharArray();
		
		if (n == 1) {
		}
		else if (k == 2) {
			char[] s1 = new char[n];
			char[] s2 = new char[n];
			
			int change1 = 0;
			int change2 = 0;
			
			for (int i = 0; i < n; i++) {
				if (i % 2 == 0) {
					if (str[i] == 'A') {
						change2++;
					}
					else if (str[i] == 'B') {
						change1++;
					}
					
					s1[i] = 'A';
					s2[i] = 'B';
				}
				else {
					if (str[i] == 'A') {
						change1++;
					}
					else if (str[i] == 'B') {
						change2++;
					}
					
					s1[i] = 'B';
					s2[i] = 'A';
				}
			}
			
			if (change1 < change2) {
				changes = change1;
				str = s1;
			}
			else {
				changes = change2;
				str = s2;
			}
		}
		else {
			int index = 0;
			while (index < n) {
				char c = str[index];
				int length = 1;
				int startIndex = index;
				
				while (index + 1 < n && str[index+1] == c) {
					index++;
					length++;
				}
				
				if (length > 1) {
					changes += length / 2;
					
					char newColor = 'A';
					
					if (length % 2 == 0) {
						newColor = getNewColor(c, (startIndex == 0 ? 'z' : str[startIndex-1]));
					}
					else {
						newColor = getNewColor(c, 'z');
						startIndex++;
					}
					
					for (int i = startIndex; i <= index; i += 2) {
						str[i] = newColor;
					}
				}
				
				index++;
			}
		}
		
		out.println(changes);
		out.println(new String(str));
		
		
		out.close();
	}
	
	public static char getNewColor(char c1, char c2) {
		char newColor = 'A';
		
		for (char c = 'A'; c <= 'C'; c++) {
			if (c != c1 && c != c2) {
				newColor = c;
				break;
			}
		}
		
		return newColor;
	}
}