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

    private static StringBuilder s;

    private static int repeatingLength(int i) {
        char c = s.charAt(i);
        int tempI = i+1;
        while (tempI<s.length() && s.charAt(tempI) == c)
            tempI++;
        
        return tempI-i;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();


        int ans = 0;
        s = new StringBuilder(sc.next());


        //k==2 to add
        if (k==2)
        {
            int tempans1 = 0;
            StringBuilder temps = new StringBuilder("");
            for (int i = 0; i < n; ++i)
            {
                temps.append((char)('A'+i%2));
                if (s.charAt(i)!=temps.charAt(i))
                    tempans1++;
            }
            int tempans2 = 0;
            StringBuilder temps2 = new StringBuilder("");
            for (int i = 0; i < n; ++i)
            {
                temps2.append((char)('B'-i%2));
                if (s.charAt(i)!=temps2.charAt(i))
                    tempans2++;
            }
            if (tempans1<tempans2)
            {
                System.out.println(tempans1);
                System.out.println(temps);
                return;
            }
            else
            {
                System.out.println(tempans2);
                System.out.println(temps2);
                return;
            }
        }

        // k>2
        for (int i = 0; i < n; ++i)
        {
            int temp = repeatingLength(i);
            if (temp > 1)
                if (temp % 2==1)
                {
                    for (int j = i+1; j < i+temp; j+=2)
                        for (int l = 0; l < k; ++l)
                            if ((char) (l+'A') != s.charAt(j-1))
                            {
                                s.setCharAt(j, (char) (l+'A'));
                                ans++;
                                break;
                            }
                    i += temp-1;
                }
                else
                {
                    if (i == 0)
                    {
                        for (int j = i; j < i+temp; j+=2)
                            for (int l = 0; l < k; ++l)
                                if ( j==n-1 || (char) (l+'A') != s.charAt(j+1))
                                    if ( j==0 || (char) (l+'A') != s.charAt(j-1))
                                    {
                                        s.setCharAt(j, (char) (l+'A'));
                                        ans++;
                                        break;
                                    }
                    }
                    else
                    {
                        if (i+temp == n)
                        {
                            for (int j = i+1; j < i+temp; j+=2)
                                for (int l = 0; l < k; ++l)
                                    if ( j==n-1 || (char) (l+'A') != s.charAt(j+1))
                                        if ( j==0 || (char) (l+'A') != s.charAt(j-1))
                                        {
                                            s.setCharAt(j, (char) (l+'A'));
                                            ans++;
                                            break;
                                        }
                        }
                        else
                            for (int j = i; j < i+temp; j+=2)
                                for (int l = 0; l < k; ++l)
                                    if ( j==n-1 || (char) (l+'A') != s.charAt(j+1))
                                        if ( j==0 || (char) (l+'A') != s.charAt(j-1))
                                        {
                                            s.setCharAt(j, (char) (l+'A'));
                                            ans++;
                                            break;
                                        }
                    }
                    i += temp-1;
                }
        }

        System.out.println(ans);
        System.out.println(s);

    }

}