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 ColorStripe {
    private Scanner scan = new Scanner(System.in);
    private int n,k;
    private StringBuffer sb = new StringBuffer();
    private String input;
    private char[] colorSet;
    
    public void inputReader() {
         n = scan.nextInt();
         k = scan.nextInt();
         colorSet = new char[k];
         for (int i = 0; i < k; i++) {
             colorSet[i] = (char) (i + 'A');
         }
         input = scan.next();
    }
    
    private String convertChar2Num(String sb) {
        String result = "";
        for(int i = 0; i < sb.length(); i++) {
            char tmp = sb.charAt(i);
            int tmp1 = tmp - 'A';
            result += tmp1;
        }
        return result;
    }
    
    public void solve() {
        int count = 0;
        char[] inputs = input.toCharArray();

        if(input.length() == 1) {
            System.out.println(count);
            System.out.println(input);
            return;
        }
            
        if(k==2 ) {
            char[] ret1 = new char[n];
            char[] ret2 = new char[n];
            for(int i = 0; i < n; i++) {
                if(i%2 == 0) {
                    ret1[i] = 'A';
                    ret2[i] = 'B';
                }else {
                    ret2[i] = 'A';
                    ret1[i] = 'B';
                }
            }
            int ret3 =0;
            int ret4 =0;
            for(int i = 0; i < n; i++) {
                if(ret1[i] != inputs[i])
                    ret3++;
                if(ret2[i] != inputs[i])
                    ret4++;
            }
            if(ret3 <= ret4){
                System.out.println(ret3);
                System.out.println(new String(ret1));
            }else{
                System.out.println(ret4);
                System.out.println(new String(ret2));

            }
                
            return;
        }
        
        
        for (int i = 1; i < inputs.length -1 ; i++) {
            char tmp1 = inputs[i-1];
            char tmp2 = inputs[i];
            char tmp3 = inputs[i+1];
            if(tmp1 == tmp2) {
                for (char color : colorSet) {
                    if(color != tmp3 && color != tmp1){
                        inputs[i] = color;
                        count++;
                        break;
                    }
                }
            }
        }
        char tmp = inputs[inputs.length - 1];
        char tmp1 = inputs[inputs.length - 2];
        if(tmp==tmp1) {
            for (char color : colorSet) {
                if(color != tmp1){
                    inputs[inputs.length - 1] = color;
                    count++;
                    break;
                }
            }
        }
        System.out.println(count);
        System.out.println(new String(inputs));
    }
    
    public static void main(String[] args) {
        ColorStripe cs = new ColorStripe();
        cs.inputReader();
        cs.solve();
    }
}