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


public  class Solution {

    static void solver(int n , char a[]){
        int tt = 0 ;
        int tt2 = 0 ;
        char temp[] = Arrays.copyOf(a , a.length) ;

        char prev = 'A' ;
        for (int i = 0; i <n ; i++) {
            if (temp[i] != prev){
                tt++ ;
                temp[i] = prev ;
            }
            if (prev == 'A')prev = 'B' ;
            else prev = 'A' ;
        }
        prev = 'B' ;
        for (int i = 0; i <n ; i++) {
            if (a[i] != prev){
                tt2++ ;
                a[i] = prev ;
            }
            if (prev == 'A')prev = 'B' ;
            else prev = 'A' ;
        }

       if (tt < tt2){
           System.out.println(tt);
           System.out.println(temp);
       }
       else {
           System.out.println(tt2);
           System.out.println(a);
       }



    }


    public static void main(String[] args) {

        int n = fsca.nextInt() ;
        int k = fsca.nextInt() ;
        char a[] = fsca.next().toCharArray() ;
        int cnt = 0 ;

        if (k == 2){
            solver(n , a);
            return;
        }
        if (n == 2){
            if (a[0] == a[1]){
                if (a[0] != 'A')a[0] = 'A' ;
                else a[0] = 'B' ;
                System.out.println(1);
                System.out.println(new String(a));
                return;
            }
        }



        for (int i = 1; i <n-1 ; i++) {
            if (a[i] == a[i-1] && a[i] == a[i+1]){
                cnt++ ;
                if (a[i-1] == 'A')a[i] = 'B' ;
                else a[i] = 'A' ;

            }

        }

        for (int i = 1; i <n-1 ; i++) {
            if (a[i] == a[i-1] || a[i] == a[i+1]){
                cnt++ ;
                if (a[i-1] != 'A' && a[i+1] != 'A')a[i] = 'A' ;
                else if(a[i-1] != 'B' && a[i+1] != 'B')a[i] = 'B';
                else a[i] = 'C' ;
            }
        }


        System.out.println(cnt);
        System.out.println(new String(a));













        fop.flush();
        fop.close();
    }


    /*-----------------------------------------------------------------------------------------------------------------------------------------------*/

    static PrintWriter fop = new PrintWriter(System.out);
    static FastScanner fsca = new FastScanner();


    static long gcd(long a, long b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
    static int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }

   // Arrays.sort() takes o(n^2) time to sort when array is reverse sorted
   // so always shuffle the array before sorting
    static final Random random = new Random();
    static void ruffleSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i]; a[i] = temp;
        }
        Arrays.sort(a);
    }

    static void ruffleSort(long[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n);
            long temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }


    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        // For Integer matrix input :
        int[][] readMat(int n, int m) {
            int a[][] = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    a[i][j] = nextInt();
            return a;
        }
        // For Character matrix input :
        char[][] readCharMat(int n, int m) {
            char a[][] = new char[n][m];
            for (int i = 0; i < n; i++) {
                String s = next();
                for (int j = 0; j < m; j++)
                    a[i][j] = s.charAt(j);
            }
            return a;
        }

        // int arrat input
        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }
        // long array input
        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

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

}