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.ArrayList;
import java.util.Scanner;
public class Main{
		Scanner sc = new Scanner(System.in);
		public static void main(String[] args) {
				Main m = new Main();
				m.run();
		} 
		public void run(){
				//main
				int n = sc.nextInt();
				int k = sc.nextInt();
				
				sc.nextLine();
				String letters = sc.nextLine();

				int firstColor = 0;
				int[] colors = new int[n + 2];
				colors[0] = -1;
				colors[n + 1] = -1;
				boolean[] needChange = new boolean[n + 2];
				for (int i = 0; i < n; i++) {
					colors[i + 1] = letters.charAt(i) - 'A';
					if (i > 0) {
						needChange[i + 1] = (colors[i + 1] == colors[i]);
					}
					//System.out.printf("%d:%d, %b%n",i+1,colors[i + 1],needChange[i + 1]);
				}

				int changeTime = 0;
				if (k == 2) {
					int[] a_colors = new int[n+2];
					int[] b_colors = new int[n+2];
					a_colors[0] = -1;
					b_colors[0] = -1;
					a_colors[n + 1] = -1;
					b_colors[n + 1] = -1;

					int a_modi = 0;
					int b_modi = 0;
					for (int i = 1; i < n + 1; i++) {
						a_colors[i] = (i + 1) % 2;
						b_colors[i] = i % 2;
						if (a_colors[i] != colors[i]) { a_modi++; }
						if (b_colors[i] != colors[i]) { b_modi++; }
					}
					if (a_modi < b_modi) {
							System.out.println(a_modi);
							System.out.println(turnStr(a_colors));
					} else {
							System.out.println(b_modi);
							System.out.println(turnStr(b_colors));
					}
					return;
				}

				for (int i = 0; i < n + 1; i++) {
					if (needChange[i]) {
						changeTime++;
						colors[i] = 0;
						while(colors[i] == colors[i-1] || colors[i] == colors[i+1]) { 
							colors[i]++;
						}
						needChange[i + 1] = false;
					}
					//System.out.printf("%d:%d, %b%n",i,colors[i],needChange[i]);
				}
				System.out.println(changeTime);
				System.out.println(turnStr(colors));
				
		}
		public String turnStr(int[] col){
				int n = col.length - 2;
				char[] charCol = new char[n];
				for (int i = 1 ; i < n + 1; i++) {
					charCol[i - 1] =   (char)((int)'A' + col[i] ) ;
				}
				return String.valueOf(charCol);
		}
}