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 c {

    Scanner scan = new Scanner(System.in);

    void run() {
        int n = scan.nextInt();
        int k = scan.nextInt();
        String s = scan.next();
        StringBuilder ans=new StringBuilder();
        int cnt=0;
        if (k == 2) {
            int f1=0,f2=0;
            int g1=0,g2=0;
            for(int i=0;i<n;i+=2)
                if(s.charAt(i)!='A')
                    f1++;
                else
                    f2++;
            for(int i=1;i<n;i+=2)
                if(s.charAt(i)!='B')
                    g1++;
                else
                    g2++;
            if(f1+g1<f2+g2){
                cnt=f1+g1;
                for(int i=0;i<n;i++)
                    if(i%2==0)
                        ans.append('A');
                    else
                        ans.append('B');
            }
            else{
                cnt=f2+g2;
                for(int i=0;i<n;i++)
                    if(i%2==0)
                        ans.append('B');
                    else
                        ans.append('A');
            }
        }
        else{
            int i=0,j=0;
            while(i<n)
            {
                j=i;
                while(j<n-1&&s.charAt(j)==s.charAt(j+1))
                    j++;
                cnt+=(j-i+1)/2;
                char temp='A';
                while(temp==s.charAt(i)||(j<n-1&&s.charAt(j+1)==temp))
                     temp++;
                for(int p=i;p<=j;p+=2)
                {
                    ans.append(s.charAt(p));
                    if(p+1<=j)
                        ans.append(temp);
                }
                i=j+1;
            }
        }
        System.out.println(cnt);
        System.out.println(ans);
    }

    public static void main(String args[]) {
        new c().run();
    }
}