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.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

public class Main {
	public static void main(String[] args) throws IOException {
		(new Main()).solve();
	}

	public Main() {
	}
	
	MyReader in = new MyReader();
	PrintWriter out = new PrintWriter(System.out);
	
	void solve() throws IOException {
		//BufferedReader in = new BufferedReader(new
		//InputStreamReader(System.in));
		//Scanner in = new Scanner(System.in);
		//Scanner in = new Scanner(new FileReader("input.txt"));
		//PrintWriter out = new PrintWriter("output.txt");
		int n = in.nextInt();
		int k = in.nextInt();
		String s = in.nextString();
		if (k == 2) {
			int count1 = 0;
			int count2 = 0;
			StringBuilder sb1 = new StringBuilder();
			StringBuilder sb2 = new StringBuilder();
			for (int i = 0; i < n; i++) {
				char ch = i % 2 == 0 ? 'A' : 'B';
				sb1.append(ch);
				if (s.charAt(i) != ch) {
					count1++;
				}
				ch = i % 2 == 1 ? 'A' : 'B';
				sb2.append(ch);
				if (s.charAt(i) != ch) {
					count2++;
				}
			}
			if (count1 < count2) {
				out.println(count1);
				out.println(sb1.toString());
			} else {
				out.println(count2);
				out.println(sb2.toString());
			}
		} else {
			int ind = 1;
			int count = 0;
			StringBuilder sb = new StringBuilder();
			sb.append(s.charAt(0));
			while (ind < n) {
				if (s.charAt(ind) == s.charAt(ind - 1)) {
					if ('A' != s.charAt(ind) && (ind == n - 1 || 'A' != s.charAt(ind + 1))) {
						sb.append('A');
					} else if ('B' != s.charAt(ind) && (ind == n - 1 || 'B' != s.charAt(ind + 1))) {
						sb.append('B');
					} else {
						sb.append('C');
					}
					if (ind < n - 1) {
						sb.append(s.charAt(ind + 1));
						ind++;
					}
					ind++;
					count++;
				} else {
					sb.append(s.charAt(ind));
					ind++;
				}
			}
			out.println(count);
			out.println(sb.toString());
		}
		
		out.close();
	}
	
	class MyReader {
		private BufferedReader in;
		String[] parsed;
		int index = 0;

		public MyReader() {
			in = new BufferedReader(new InputStreamReader(System.in));
		}

		public int nextInt() throws NumberFormatException, IOException {
			if (parsed == null || parsed.length == index) {
				read();
			}
			return Integer.parseInt(parsed[index++]);
		}

		public long nextLong() throws NumberFormatException, IOException {
			if (parsed == null || parsed.length == index) {
				read();
			}
			return Long.parseLong(parsed[index++]);
		}
		
		public double nextDouble() throws NumberFormatException, IOException {
			if (parsed == null || parsed.length == index) {
				read();
			}
			return Double.parseDouble(parsed[index++]);
		}
		
		public String nextString() throws IOException {
			if (parsed == null || parsed.length == index) {
				read();
			}
			return parsed[index++];
		}

		private void read() throws IOException {
			parsed = in.readLine().split(" ");
			index = 0;
		}

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

};