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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

import java.util.*;


public class Soly
{
    static final int INF = Integer.MAX_VALUE;

    static int mergeSort(int[] a,int [] c, int begin, int end)
    {
        int inversion=0;
        if(begin < end)
        {
            inversion=0;
            int mid = (begin + end) >>1;
            inversion+= mergeSort(a,c, begin, mid);
            inversion+=mergeSort(a, c,mid + 1, end);
            inversion+=merge(a,c, begin, mid, end);
        }
        return inversion;
    }
/////////////////////////////////////////////////////

    static int  merge(int[] a,int[]c, int b, int mid, int e)
    {
        int n1 = mid - b + 1;
        int n2 = e - mid;
        int[] L = new int[n1+1], R = new int[n2+1];
        int[] L1 = new int[n1+1], R1 = new int[n2+1];
        //inversion
        int inversion=0;

        for(int i = 0; i < n1; i++) {
            L[i] = a[b + i];
            L1[i] = c[b + i];
        }
        for(int i = 0; i < n2; i++)  {
            R[i] = a[mid + 1 + i];
            R1[i] = c[mid + 1 + i];
        }
        L[n1] = R[n2] = INF;

        for(int k = b, i = 0, j = 0; k <= e; k++)
            if(L[i] <= R[j]){
                a[k] = L[i];
                c[k] = L1[i++];
            }

            else
            {
                a[k] = R[j];
                c[k] = R1[j++];
                inversion=inversion+(n1-i);

            }
        return inversion;

    }
    //////////////////////////////////////////////////////////////
static int l;
 static int va(char[]a){
     Stack<Character>s= new Stack<>();
     int op=0,c=0;
     for (int p = 0; p < a.length; p++) {
         if (a[p]==')'){
             if (!s.isEmpty()){
                 if (s.peek()=='('){
                     op--;
                     s.pop();
                 }
                 else{
                     ++c;
                     s.push(')');
                 }
             }
             else {
                 ++c;
                 s.push(')');
             }
         }
         else if(a[p]=='(') {
             ++op;
             if (!s.isEmpty()){
                 if (s.peek()=='('){
                     s.push(a[p]);
                 }
                 else s.push('(');
             }
             else s.push('(');
         }
     }
     if (s.isEmpty())return 0;
     else {
         if (op>0&&c>0)return 50;
         if (s.peek()=='('){
             //1 opening
             l=s.size();
             return 1;
         }
         else {
             //2 closing
             l=s.size();
             return 2;
         }
     }

 }

/////////////////////////////////////////////////////////////////////////////////
    static public int maxSubArray(int[] nums) {
        boolean s= false,s2=false;
       int ans2=Integer.MIN_VALUE;
        int ans=0,sum=0;
       for (int i = 0; i < nums.length; i++) {
           if (nums[i]>=0)s=true;
           if (nums[i]<0)s2=true;
           ans2=Math.max(ans2,nums[i]);
           if (sum+nums[i]>0)sum+=nums[i];
           else sum=0;
           ans=Math.max(ans,sum);
       }
       if (!s2)return ans;
       if (!s)return ans2;
       else {
           return ans;

       }
   }



    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        try (PrintWriter or = new PrintWriter(System.out)) {
           int n = in.nextInt(),k=in.nextInt();
           char[] a= in.next().toCharArray();
           int ans=0;
            if (k == 2){
                StringBuilder w1=new StringBuilder(),w2=new StringBuilder();
                int w1d=0,w2d=0;
                for (int i=0; i<n; i++){
                    if (i%2 == 0){
                        w1.append('A');
                        w2.append('B');
                    }
                    else {
                        w2.append('A');
                        w1.append('B');
                    }
                    if (a[i] == w1.charAt(i)) w1d++;
                    else w2d++;
                }
                if (w1d > w2d)
                   or.println( w2d +"\n"+w1);
                else
                    or.println( w1d +"\n"+w2);
            }
            else {
                for (int i = 0; i < n - 1; i++) {
                    if (a[i] == a[i + 1]) {
                        ++ans;
                        if (i + 2 < n) {
                            for (int j = 0; j < k; j++) {
                                char c = (char) ('A' + j);
                                if (c != a[i] && c != a[i + 2]) {
                                    a[i + 1] = c;
                                    break;
                                }
                            }
                        } else {
                            for (int j = 0; j < k; j++) {
                                char c = (char) ('A' + j);
                                if (c != a[i]) {
                                    a[i + 1] = c;
                                    break;
                                }
                            }
                        }
                    }
                }
                or.println(ans);
                or.println(new String(a));
            }

        }
    }


    static class Scanner {

        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

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

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

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++) {
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec) {
                        f *= 10;
                    }
                }
            }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

    }


}
class  Triple{
   int r,c,x,y;
    public Triple(int r, int c, int x, int y) {
        this.r = r;
        this.c = c;
        this.x = x;
        this.y = y;
    }
}