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.StringTokenizer;

public class Main {
    static void zap() throws IOException {
        int n = nextInt();
        int k = nextInt();
        int count = 0;
        String word = nextToken();
        StringBuffer sb = new StringBuffer(word);
        if(k == 2)
        {
            for(int i=0;i<sb.length();i++)
                sb.setCharAt(i, i % 2 == 0 ? 'A' : 'B');
            int diff1 = 0;
            for(int i=0;i<sb.length();i++)
                if(sb.charAt(i) != word.charAt(i))
                    diff1++;
            StringBuffer sb2 = new StringBuffer(word);
            for(int i=0;i<sb2.length();i++)
                sb2.setCharAt(i, i % 2 == 1 ? 'A' : 'B');
            int diff2 = 0;
            for(int i=0;i<sb2.length();i++)
                if(sb2.charAt(i) != word.charAt(i))
                    diff2++;
            if(diff1 < diff2)
            {
                out.println(diff1);
                out.println(sb);
            }
            else
            {
                out.println(diff2 + "\n" + sb2);
            }
            return;
        }
        for(int i=0;i<sb.length()-1;i++)
        {
            char next = sb.charAt(i+1);
            if(sb.charAt(i) != next)
                continue;
            for(int j=0;j<k;j++)
            {
                char consider = (char)('A'+j);
                if(consider != next)
                {
                    if(i <= sb.length()-3)
                    {
                        if(consider != sb.charAt(i+2))
                        {
                            sb.setCharAt(i+1, consider);
                            break;
                        }
                        else if(i > 0)
                        {
                            if(consider != sb.charAt(i-1))
                            {
                                sb.setCharAt(i, consider);
                                break;
                            }
                        }
                        else
                        {
                            sb.setCharAt(i, consider);
                            break;
                        }
                    }
                    else
                    {
                        sb.setCharAt(i+1, consider);
                        break;
                    }
                }
            }
            count++;
        }
        out.println(count);
        out.println(sb);
    }

    static BufferedReader br;
    static StringTokenizer st;
    static PrintWriter out;

    public static void main(String[] args) throws IOException {
        InputStream input = System.in;
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(System.out);
        zap();
        out.close();
    }

    static long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    static String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = br.readLine();
            if (line == null) {
                return null;
            }
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
}