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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class B {

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

		int n = sc.nextInt(), k = sc.nextInt();
		char[] s = sc.next().toCharArray();
		if(k > 2)
			out.printf("%d\n%s\n", solveMore(s, n), new String(s));
		else
			out.printf("%d\n%s\n", solveBi(s, n), new String(s));
		out.flush();
		out.close();

	}
	
	static int solveMore(char[] s, int n)
	{
		int x = 0;
		for(int i = 1; i < n; ++i)
			if(s[i] == s[i - 1])
				for(char c = 'A'; c <= 'C'; ++c)
					if(c != s[i - 1] && (i == n - 1 || c != s[i + 1]))
					{
						s[i] = c;
						++x;
						break;
					}
		return x;
	}
	
	static int solveBi(char[] s, int n)
	{
		int x = 0, y = 0;
		char cx = 'A', cy = 'B', tmp;
		for(int i = 0; i < n; ++i)
		{
			if(s[i] != cx)
				++x;
			if(s[i] != cy)
				++y;
			tmp = cx;
			cx = cy;
			cy = tmp;
		}
		cx = x < y ? 'A' : 'B';
		for(int i = 0; i < n; ++i, cx = (char) ((cx - 'A' + 1)%2 + 'A'))
			s[i] = cx;
		return Math.min(x, y);
	}

	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 boolean ready() throws IOException {return br.ready();}
	}
}