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.*;

public class cf171{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        String s=sc.next();
        int i=0;
        StringBuilder ans=new StringBuilder();
        ans.append("$");
        int c=0;
        StringBuilder ret=new StringBuilder();
        int t2=n;
        s="$"+s+"$";
        while(t2>0)
        {
            ret.append('A');
            t2--;
            if(t2>0)
            {
                ret.append('B');
            }
            t2--;
        }
        if(k==2)
        {
            int t1=0;
            for(i=1;i<=n;i=i+2)
            {
                char ch=s.charAt(i);
                if(ch!='A')
                {
                    t1++;
                }
            }
            for(i=2;i<=n;i=i+2)
            {
                char ch=s.charAt(i);
                if(ch!='B')
                {
                    t1++;
                }
            }
            if(t1<n-t1)
            {
                System.out.println(t1);
                System.out.println(String.valueOf(ret));
            }
            else
            {
                StringBuilder temp1=new StringBuilder();
                for(i=0;i<n;i++)
                {
                    if(ret.charAt(i)=='A')
                    {
                        temp1.append('B');
                    }
                    else
                    {
                        temp1.append('A');
                    }
                }
                System.out.println(n-t1);
                System.out.println(String.valueOf(temp1));
            }
            return;
        }
        
        for(i=1;i<=n;i++)
        {
            char ch=s.charAt(i);
            if(ch!=ans.charAt(i-1))
            {
                ans.append(ch);
            }
            else
            {
                char ch1=ans.charAt(i-1);
                char ch2=s.charAt(i+1);
                for(int t=0;t<k;t++)
                {
                    char temp=(char)(t+'A');
                    if(temp!=ch1&&temp!=ch2)
                    {
                        ans.append(temp);
                        c++;
                        break;
                    }
                }
            }
            //System.out.println(ans);
        }
        System.out.println(c);
        System.out.println(String.valueOf(ans).substring(1));
        
    }
}