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.Scanner;


public class ColorStripeNew {
	public static void main(String[] args) {
		
		ColorStripeNew cs = new ColorStripeNew();
		
		Scanner sc = new Scanner(System.in);
		
		int num_cells = sc.nextInt();
		int colors = sc.nextInt();
		String stripes = sc.next();
		
		if (colors == 2)
		{
			// Just test both and see which one works better.
			int repaints = 0;
			StringBuilder sb = new StringBuilder("");
			for (int i = 0; i < num_cells; i++)
			{
				if (i % 2 == 0)
				{
					sb.append('A');
					if (stripes.charAt(i) == 'B')
					{
						repaints += 1;
					}
				}
				else
				{
					sb.append('B');
					if (stripes.charAt(i) == 'A')
					{
						repaints += 1;
					}	
				}
			}
			
			if (repaints < num_cells-repaints)
			{
				System.out.println(repaints);
				System.out.println(sb.toString());
			}
			else
			{
				System.out.println(num_cells-repaints);
				sb.deleteCharAt(0);
				if (sb.charAt(sb.length()-1) == 'B')
				{
					sb.append('A');
				}
				else
				{
					sb.append('B');
				}
				System.out.println(sb.toString());
			}
		}
		
		else
		{
			int[][] traceback = new int[2][num_cells-1];
			// First entry represents "didn't paint previous cell", second
			// entry represents "painted previous cell"
			int[] num_repaints = {0,1};
			
			for (int i = 1; i < num_cells; i++)
			{
				int paint;
				if (num_repaints[0] < num_repaints[1])
				{
					paint = num_repaints[0] + 1;
				}
				else
				{
					paint = num_repaints[1] + 1;
					traceback[1][i-1] = 1;
				}
				
				int nopaint;
				if (stripes.charAt(i-1) == stripes.charAt(i))
				{
					nopaint = num_repaints[1];
					traceback[0][i-1] = 1;
				}
				else
				{
					if (num_repaints[0] < num_repaints[1])
					{
						nopaint = num_repaints[0];
					}
					else
					{
						nopaint = num_repaints[1];
						traceback[0][i-1] = 1;
					}
				}
				
				num_repaints[0] = nopaint;
				num_repaints[1] = paint;
			}
			
			System.out.println(Math.min(num_repaints[0],num_repaints[1]));
			
			// Generate paint sequence
			StringBuilder sb = new StringBuilder();
			
			int current_status = -1;
			char nextChar;
			
			if (num_repaints[0] > num_repaints[1])
			{
				
				current_status = 1;
				nextChar = cs.findLetterNot(stripes.charAt(stripes.length()-1), stripes.charAt(stripes.length()-1));
			}
			else
			{
				current_status = 0;
				nextChar = stripes.charAt(stripes.length()-1);
			}
			sb.append(nextChar);
			
			for (int i = 0; i < traceback[0].length; i++)
			{
				//System.out.printf("%d ",traceback[0][i]);
				//System.out.printf("%d \n",traceback[1][i]);
			}
			
			for (int i = num_cells - 2; i >= 0; i--)
			{
				//System.out.println(current_status);
				current_status = traceback[current_status][i];
				if (current_status == 0)
				{
					nextChar = stripes.charAt(i);
				}
				else
				{
					if (i == 0)
					{
						nextChar = cs.findLetterNot(nextChar, nextChar); 
					}
					else
					{
						nextChar = cs.findLetterNot(nextChar, stripes.charAt(i-1));
					}
				}
				sb.append(nextChar);
			}
			
			sb = sb.reverse();
			System.out.println(sb.toString());
		}
	}
	
	public char findLetterNot(char letterOne, char letterTwo)
	{
		if (!(letterOne == 'A') && !(letterTwo == 'A'))
		{
			return 'A';
		}
		else if (!(letterOne == 'B') && !(letterTwo == 'B'))
		{
			return 'B';
		}
		return 'C';
		
	}
}