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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author zodiacLeo
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC
    {
        private int k;
        private int n;
        private char[] a;

        public void solve(int testNumber, FastScanner in, PrintWriter out)
        {
            n = in.nextInt();
            k = in.nextInt();
            a = in.next().toCharArray();
            if (k == 1)
            {
                out.println(0);
                for (int i = 0; i < n; i++)
                {
                    out.print(a[i]);
                }
            } else if (k == 2)
            {
                char A[] = new char[n];
                char B[] = new char[n];
                A[0] = 'A';
                B[0] = 'B';
                for (int i = 1; i < n; i++)
                {
                    A[i] = (A[i - 1] == 'A') ? 'B' : 'A';
                    B[i] = (B[i - 1] == 'A') ? 'B' : 'A';
                }

                int c1 = 0;
                int c2 = 0;
                for (int i = 0; i < n; i++)
                {
                    if (A[i] != a[i])
                    {
                        c1++;
                    }
                    if (B[i] != a[i])
                    {
                        c2++;
                    }
                }
                int c = 0;
                char t[];
                if (c1 < c2)
                {
                    c = c1;
                    t = A;
                } else
                {
                    c = c2;
                    t = B;
                }
                out.println(c);
                for (int i = 0; i < n; i++)
                {
                    out.print(t[i]);
                }
            } else
            {
                int start = 0;
                int count = 0;
                for (int i = 1; i <= n; i++)
                {
                    if ((i < n && a[i] != a[i - 1]) || (i == n && start != i))
                    {
                        int length = i - start;
                        if (length >= 2)
                        {
                            char c = 'A';
                            for (char kk = 'A'; kk < 'A' + k; kk++)
                            {
                                if (length % 2 == 0 && kk != a[start] && ((i < n && kk != a[i]) || i == n))
                                {
                                    c = kk;
                                    break;
                                }
                                if (length % 2 != 0 && kk != a[start])
                                {
                                    c = kk;
                                    break;
                                }
                            }
                            for (int j = ((length % 2 == 0) ? i - 1 : i - 2); j > start && j >= 0; j -= 2)
                            {
                                a[j] = c;
                                count++;
                            }
                        }
                        start = i;
                    }
                }
                out.println(count);
                for (int i = 0; i < n; i++)
                {
                    out.print(a[i]);
                }
            }
        }

    }

    static class FastScanner
    {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream is)
        {
            br = new BufferedReader(new InputStreamReader(is));
        }

        public FastScanner(File f)
        {
            try
            {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e)
            {
                e.printStackTrace();
            }
        }

        public String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                String s = null;
                try
                {
                    s = br.readLine();
                } catch (IOException e)
                {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public int nextInt()
        {
            return Integer.parseInt(next());
        }

    }
}