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.io.*;
import java.util.*;
public class P219C
{

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        char[] c = s.toCharArray();
        if (k == 2)
        {
            solve2(n, c);
        }
        else
        {
            solve(n, k, c);
        }
    }
    
    private static void solve2(int n, char[] c)
    {
        int count = 0, count2 = 0;
        for (int i = 0; i < n; i++)
        {
            char p = (i % 2 == 0) ? 'A' : 'B';
            if (c[i] != p) count++;
        }
        for (int i = 0; i < n; i++)
        {
            char p = (i % 2 == 1) ? 'A' : 'B';
            if (c[i] != p) count2++;
        }
        if (count < count2)
        {
            System.out.println(count);
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                    System.out.print("A");
                else
                    System.out.print("B");
            }
            System.out.println();
        }
        else
        {
            System.out.println(count2);
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                    System.out.print("B");
                else
                    System.out.print("A");
            }
            System.out.println();
        }
    }
    
    private static void solve(int n, int k, char[] c)
    {
        int start = 0;
        int pos = 1;
        int count = 0;
        while (pos < c.length)
        {
            if (c[pos] != c[pos-1])
            {
                int len = pos - start;
                if (len == 1)
                {
                    start = pos;
                    pos++;
                    continue;
                }
                if (len % 2 == 1)
                {
                    char rep = c[start] == 'A' ? 'B' : 'A';
                    for (int i = start + 1; i < pos; i+=2)
                    {
                        c[i] = rep;
                        count++;
                    }
                }
                else
                {
                    char rep = c[start] == 'A' ? 'B' : 'A';
                    for (int i = start + 1; i < pos - 1; i+=2)
                    {
                        c[i] = rep;
                        count++;
                    }
                    if (c[pos-1] != 'A' && c[pos] != 'A')
                    {
                        c[pos-1] = 'A';
                    }
                    else if (c[pos-1] != 'B' && c[pos] != 'B')
                    {
                        c[pos-1] = 'B';
                    }
                    else
                    {
                        c[pos-1] = 'C';
                    }
                    count++;
                }
                start = pos;
            }
            pos++;
        }
        int len = n - start;
        if (len > 1)
        {
            char rep = c[start] == 'A' ? 'B' : 'A';
            for (int i = start + 1; i < n; i+=2)
            {
                c[i] = rep;
                count++;
            }
        }
        System.out.println(count);
        for (int i = 0; i < n;i++)
        {
            System.out.print(c[i]);
        }
        System.out.println();
    }

}