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.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class ColorStripe
{
	static int[][] memo;
	static int k;
	static int n;
	static char[] arr;
	static String[][] word;
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		arr = sc.next().toCharArray();
		
		memo = new int[n+1][27];
		word = new String[n+1][27];
		
		for (int i = 0; i < memo.length; i++)
			Arrays.fill(memo[i], -1);
		
		System.out.println(solve(0, 26));
		print(0, 26);
		pw.flush();
		pw.close();
		sc.close();
	}
	private static void print(int ind, int last)
	{
		if(ind == n)
			return;
		
		for (int i = 0; i < k; i++)
		{
			if(i == last)
				continue;
			
			if(i + 'A' == arr[ind] && solve(ind+1, i) == memo[ind][last])
			{
				pw.print((char)('A' + i));
				print(ind+1, i);
				break;
			}
			else
			  if(memo[ind][last] == 1 + solve(ind+1, i))
			  {
				pw.print((char)('A' + i));
				print(ind+1, i);
				break;
			  }
		}
	}
	
	private static int solve(int ind, int last)
	{
		if(ind == n)
			return 0;
		
		if(memo[ind][last] != -1)
			return memo[ind][last];
		
		int ans = (int)1e9;
		for (int i = 0; i < Math.min(k, 3); i++)
		{
			if(i == last)
				continue;
			
			if(i + 'A' == arr[ind])
				ans = Math.min(ans, solve(ind+1, i));
			else
				ans = Math.min(ans, 1 + solve(ind+1, i));
		}
		if(arr[ind] - 'A' != last)
			ans = Math.min(ans, solve(ind+1, arr[ind] - 'A'));
		
		return memo[ind][last] = ans;
	}
}