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 Prob219C {
	public static void main(String[] Args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int colors = scan.nextInt();
		String s = scan.next();
		char[] arr = s.toCharArray();
		if (colors == 2) {
			int evenAs = 0;
			int oddBs = 0;

			for (int i = 0; i < arr.length; i++)
				if (i % 2 == 0 && arr[i] == 'A')
					evenAs++;
				else if (i % 2 == 1 && arr[i] == 'B')
					oddBs++;

			int evenBs = (x + 1) / 2 - evenAs;
			int oddAs = x / 2 - oddBs;

			if (evenAs + oddBs > evenBs + oddAs) {
				System.out.println(evenBs + oddAs);
				for (int i = 0; i < x; i++)
					System.out.print(i % 2 == 0 ? 'A' : 'B');
				System.out.println();
			} else {
				System.out.println(evenAs + oddBs);
				for (int i = 0; i < x; i++)
					System.out.print(i % 2 == 0 ? 'B' : 'A');
				System.out.println();
			}

		} else if (x == 1) {
			System.out.println(0);
			System.out.println(s);
		} else {
			int count = 0;
			StringBuffer sb = new StringBuffer();
			sb.append(arr[0]);

			for (int i = 1; i < x - 1; i++) {
				if (arr[i] == arr[i - 1]) {
					count++;
					for (int j = 0; j < 3; j++)
						if (arr[i] != 'A' + j && arr[i + 1] != 'A' + j) {
							arr[i] = (char) ('A' + j);
							break;
						}
				}
				sb.append(arr[i]);
			}

			if (arr[x - 1] == arr[x - 2]) {
				count++;
				if (arr[x - 1] == 'A')
					sb.append('C');
				else
					sb.append('A');
			} else
				sb.append(arr[x - 1]);

			System.out.println(count);
			System.out.println(sb);
		}

	}
}