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.*;
import java.math.*;

public class Main {

    FastScanner in;
    PrintWriter out;

    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException{
        new Main().run();
    }

    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }

    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public void solve() throws IOException{

        int n = in.nextInt(), k = in.nextInt();
        String str = in.next();
        if(k == 2){


            char[] s1 = new char[n];
            char[] s2 = new char[n];

            int cnt = 0;
            int start1 = 0;
            int start2 = 1;
            int diff1 = 0;
            int diff2 = 0;

            while(cnt != n){
                char c1 = (char)(start1 + 'A');
                char c2 = (char)(start2 + 'A');
                diff1 += (c1 != str.charAt(cnt) ? 1 : 0);
                diff2 += (c2 != str.charAt(cnt) ? 1 : 0);
                s1[cnt] = c1;
                s2[cnt] = c2;
                start1 = 1 - start1;
                start2 = 1 - start2;
                cnt++;
            }
            
            out.println(diff1 <= diff2 ? diff1 : diff2);
            out.println(diff1 <= diff2 ? s1 : s2);
        }else{

            int res = 0;
            char[] carr = str.toCharArray();

            for(int i = 1; i < carr.length; i++){
                if(carr[i] == carr[i - 1]){
                    res++;
                    char c = '#';
                    for(int j = 0; j < k; j++){
                        if( i != carr.length - 1 && ((char) 'A' + j) != carr[i - 1] && ((char) 'A' + j) != carr[i + 1]){
                            carr[i] = (char) ('A' + j);
                            break;
                        }else if(i == carr.length - 1 && ((char) 'A' + j) != carr[i - 1]){
                            carr[i] = (char) ('A' + j);
                            break;
                        }
                    }
                }
            }

        out.println(res);
        out.println(new String(carr));

        }

        return;
    }



}