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 Povtory_v_stroke {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        String seq=sc.next();
       if(k==2) {alph2(seq);}
       else {otherAlph(seq.toCharArray());}
    }
private static void alph2(String seq){
    int counter1=0,counter2=0;
    for(int i=0;i<seq.length();i=i+2){
        if(seq.charAt(i)=='A') {counter1++;}
        else {counter2++;}
        }
    for(int i=1;i<seq.length();i=i+2){
        if(seq.charAt(i)=='B') {counter1++;}
        else {counter2++;}
        }
    if(counter1>counter2){
        int num=seq.length()-counter1;
        System.out.println(num);
        for(int i=0;i<seq.length();i++){
            if(i%2==0){
                System.out.print('A');}
            else
                {System.out.print('B');}
            }
        }
    else{
        int num=seq.length()-counter2;
        System.out.println(num);
        for(int i=0;i<seq.length();i++){
            if(i%2==0){
                System.out.print('B');}
            else
                {System.out.print('A');}
            }
        }
    }
private static void otherAlph(char[] sec){
    char[] seq=sec;
    int counter=0;    
    for(int i=1;i<seq.length;i++){
        if(seq[i]==seq[i-1]){
            counter++;
            if(seq[i]=='A'){
                if(i==seq.length-1){seq[i]='B';}
                else{
                    if(seq[i+1]=='B'){seq[i]='C';}
                    else{seq[i]='B';}
                    }
                }
            else{
                if(seq[i]=='B'){
                    if(i==seq.length-1){seq[i]='A';}
                    else{
                        if(seq[i+1]=='A'){seq[i]='C';}
                        else{seq[i]='A';}
                        }
                    }
                else{
                    if(i==seq.length-1){seq[i]='A';}
                    else{
                        if(seq[i+1]=='A'){seq[i]='B';}
                        else{seq[i]='A';}
                        }
                    }
                }
            }
        }
    System.out.println(counter);
    for(int i=0;i<seq.length;i++){
        System.out.print(seq[i]);
    }
    }
}