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.*;
import java.lang.*;
import java.io.*;


public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        String str=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String pat=br.readLine();
        char res[]=pat.toCharArray();
        int count=0;
        if(k==2)
        {
            StringBuilder A=new StringBuilder("");
            StringBuilder B=new StringBuilder("");
            for(int i=0;i<pat.length();i++)
            {
                if(i%2==0)
                {
                    A.append("A");
                    B.append("B");
                }
                else
                {
                    A.append("B");
                    B.append("A");
                }
            }
            int counta=0,countb=0;
            for(int i=0;i<pat.length();i++)
            {
                if(A.charAt(i)!=pat.charAt(i))
                    counta++;
                if(B.charAt(i)!=pat.charAt(i))
                    countb++;
            }
            if(counta<countb)
            {
                System.out.println(counta);
                System.out.print(A);
            }
            else 
            {
                System.out.println(countb);
                System.out.print(B);
            }
            return ;
        }
        for(int i=0;i<pat.length()-1;i++)
        {
            int temp=-1;
            char ch=res[i+1];
            if(i<n-1)
            {
                if(res[i]==res[i+1])
                {
                    count++;
                    temp=(int)(res[i])-'A'+1;
                    temp++;
                    if(temp==k+1)
                        temp=1;
                    ch=(char)((temp)+'A'-1);
                    if(i+2<n)
                    {
                        if(res[i+2]==ch)
                        {
                            temp=(int)(res[i])-'A'+1;
                            temp--;
                            if(temp==0)
                                temp=k;
                            ch=(char)((temp)+'A'-1);
                        }
                    }
                }
                res[i+1]=ch;
            }
        }
        System.out.println(count);
        StringBuilder ans=new StringBuilder("");
        for(int i=0;i<res.length;i++)
            ans.append(res[i]);
        System.out.print(ans);
    }
}