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:
// http://codeforces.com/contest/270/submission/84974624
import java.math.*;
import java.util.*;
import java.io.*;
  
public class C { 
  
    static int test = 10; // 0 for local testing, 1 for std input

    static BufferedReader in;
    static PrintWriter out = new PrintWriter(System.out);
    static String file = "../in";
    static int inf = 1_000_000;

    static void swap(int[]ary, int i, int j)
    {
        int t = ary[i];
        ary[i] = ary[j];
        ary[j] = t;
    }
    
    static String[] split() throws Exception
    {
        return in.readLine().split(" ");
    }

    static int readInt() throws Exception
    {
        return Integer.valueOf(in.readLine());
    }

    static int[] toIntArray() throws Exception
    {
        String[] sp = split();
        int n = sp.length;
        int[] ary = new int[n];
        for(int i = 0; i < n; i++) ary[i] = Integer.valueOf(sp[i]);
        return ary;
    }

    static long[] toLongArray() throws Exception
    {
        String[] sp = split();
        int n = sp.length;
        long[] ary = new long[n];
        for(int i = 0; i < n; i++) ary[i] = Long.valueOf(sp[i]);
        return ary;
    }    

    public static void main(String[] args) throws Exception
    {
        int _k = Integer.valueOf("1");
        if(test > 0) in = new BufferedReader(new InputStreamReader(System.in));
        else in = new BufferedReader(new FileReader(file));
        if(test < 0) {String[] str = in.readLine().split(" ");
            char[] cc = str[0].toCharArray();
        }

        
        
        /****************************************************/  
        /****************************************************/
        /****************************************************/
        /****************************************************/

        int[] ary = toIntArray();
        char[] chars = in.readLine().toCharArray();
        int n = ary[0], k = ary[1];
        if(k == 2)
        {
            int s1 = 0, s2 = 0;
            char c1 = 'A', c2 = 'B';
            char[] ans1 = new char[n], ans2 = new char[n];
            for(int i = 0; i < n; i++)
            {
                c1 = i % 2 == 0 ? 'A' : 'B';
                c2 = i % 2 == 0 ? 'B' : 'A';
                ans1[i] = c1;
                ans2[i] = c2;
                if(c1 != chars[i]) s1++;
                if(c2 != chars[i]) s2++;
            }
            out.println(Math.min(s1, s2));
            if(s1 < s2)
            {
                out.println(String.valueOf(ans1));
            }
            else out.println(String.valueOf(ans2));
            out.flush();
            return;
        }

        // at least 3 characters
        int ans = 0;
        for(int i = 1; i < n; i++)
        {
            if(chars[i - 1] != chars[i]) continue;
            else
            {
                int c1 = chars[i - 1] - 'A';
                int c2 = c1;
                int next = (c1 + 1) % k;
                if(i + 1 < n) c2 = chars[i + 1] - 'A';
                if(next == c2) next = (next + 1) % k;
                chars[i] = (char)('A' + next);
                ans++;
                i++;
            }
        }
        out.println(ans);
        out.println(String.valueOf(chars));

        /****************************************************/
        /****************************************************/
        /****************************************************/
        /****************************************************/

        out.flush();
    }

    static boolean canPass(int initial, int[] ary)
    {
        int n = ary.length;
        int enegy = 0;
        for(int i = 0; i < n; i++)
        {
            enegy += initial - ary[i];
            if(enegy < 0) return false;
            initial = ary[i];
        }
        return true;
    }
}