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 Solution
{
    int N,K;
    
    String source;
    
    void init()
    {
        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();
        K=scan.nextInt();
        source=scan.next();
    }
    
    void work()
    {
        if (K==2)
        {
            int cnt1=0;
            int cnt2=0;
            // ABAB...
            for (int i=0;i<N;i++)
            {
                if (i%2==0)
                {
                    if (source.charAt(i)=='B')
                        cnt1++;
                }
                else
                {
                    if (source.charAt(i)=='A')
                        cnt1++;
                }
            }
            // BABA...
            for (int i=0;i<N;i++)
            {
                if (i%2==0)
                {
                    if (source.charAt(i)=='A')
                        cnt2++;
                }
                else
                {
                    if (source.charAt(i)=='B')
                        cnt2++;
                }
            }
            if (cnt1<cnt2)
            {
                StringBuilder sb=new StringBuilder();
                for (int i=0;i<N;i++)
                {
                    if (i%2==0)
                    {
                        sb.append('A');
                    }
                    else
                    {
                        sb.append('B');
                    }
                }
                System.out.println(cnt1);
                System.out.println(sb.toString());
            }
            else
            {
                StringBuilder sb=new StringBuilder();
                for (int i=0;i<N;i++)
                {
                    if (i%2==0)
                    {
                        sb.append('B');
                    }
                    else
                    {
                        sb.append('A');
                    }
                }
                System.out.println(cnt2);
                System.out.println(sb.toString());
            }
            return;
        }
        else
        {
            StringBuilder sb=new StringBuilder();
            int res=0;
            for (int i=0;i<N;)
            {
                char current=source.charAt(i);
                int start=i;
                for (;i<N && current==source.charAt(i);i++) ;
                int end=i;
                if (end-start==1)
                    sb.append(current);
                else
                {
                    char next='0';
                    if (end!=N) next=source.charAt(end);
                    char rep=another(current,next);
                    for (int k=start;k<end;k++)
                    {
                        if ((k-start)%2==0)
                        {
                            sb.append(current);
                        }
                        else
                        {
                            sb.append(rep);
                            res++;
                        }
                    }
                }
            }
            System.out.println(res);
            System.out.println(sb.toString());
        }
    }
    
    char another(char p,char q)
    {
        for (char i='A';i<='Z';i++)
        {
            if (p!=i && q!=i) return i;
        }
        return 'C';
    }
    
    void run()
    {
        init();
        work();
    }
    
    public static void main(String[] args)
    {
        new Solution().run();
    }
}