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.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

public class ssss {
    public static void main(String[] args){
        try{
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String[] ss=br.readLine().split(" ");
            int n=Integer.parseInt(ss[0]);
            int k=Integer.parseInt(ss[1]);
            String str=br.readLine();
            if(k==2){
                StringBuilder ss1=new StringBuilder(""),ss2=new StringBuilder("");
                for(int i=0;i<n;i++){
                    if(i%2==0){
                        ss1.append("A");
                        ss2.append("B");
                    }else{
                        ss2.append("A");
                        ss1.append("B");
                    }
                }
                String str1=String.valueOf(ss1),str2=String.valueOf(ss2);
                int ans1=0,ans2=0;
                for(int i=0;i<n;i++){
                    if(str.charAt(i)!=str1.charAt(i)){
                        ans1++;
                    }
                    if(str.charAt(i)!=str2.charAt(i)){
                        ans2++;
                    }
                }
                if(ans1<ans2){
                    System.out.println(ans1);
                    System.out.println(str1);
                }else{
                    System.out.println(ans2);
                    System.out.println(str2);
                }
                return;
            }

            char[] c=str.toCharArray();
            int ans=0;
            for(int j=1;j<n;j++){
                if(c[j]==c[j-1]){
                    ans++;
                    int a=(int)(c[j-1])-65;
                    if(j==n-1) {
                        a = (a + 1) % k;
                    }else{
                        int b=(int)(c[j+1])-65;
                        a=(a+1)%k;
                        while(a==b){
                            a=(a+1)%k;
                        }
                    }
                    char cc=(char)(a+65);
                    c[j]=cc;
                }
            }
            System.out.println(ans);
            System.out.println(String.valueOf(c));
        }catch(Exception e){
            System.out.println("KKKK "+e.getMessage());
        }
    }

    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
}