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.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class ColorStripe {

    /**
     * @param args
     */
    public static void main (String[] args) {

        new ColorStripe().solve();
    }

    public void solve () {
        Scanner s = new Scanner(System.in);
        int num = s.nextInt();
        int colors = s.nextInt();
        StringBuilder sequenceBuilder = new StringBuilder();
        StringBuilder sequenceBuilderTwo = new StringBuilder();
        String sequence = s.next();

        if (colors == 2) {
            int costOne = 0;
            int costTwo = 0;
            for (int i = 0; i < sequence.length(); i++) {
                if (sequence.charAt(i) == 'A') {
                    if (i % 2 == 0) {
                        costTwo++;
                    }
                    else {
                        costOne++;
                    }
                }
                else {
                    if (i % 2 == 0) {
                        costOne++;
                    }
                    else {
                        costTwo++;
                    }
                }
                if (i % 2 == 0) {
                    sequenceBuilder.append('A');
                    sequenceBuilderTwo.append('B');
                }
                else {
                    sequenceBuilder.append('B');
                    sequenceBuilderTwo.append('A');
                }
            }
            if(costOne<costTwo){
                System.out.println(costOne);
                System.out.println(sequenceBuilder.toString());
            }
            else{
                System.out.println(costTwo);
                System.out.println(sequenceBuilderTwo.toString());
            }
        }
        else {
            int cost = 0;
            StringBuilder optionStringBuilder = new StringBuilder();
            for(int i =0; i<colors; i++){
                char next = (char)('A'+i);
                optionStringBuilder.append(next);
            }
            String options = optionStringBuilder.toString();
            sequenceBuilder.append(sequence.charAt(0));
            for(int i = 1; i<sequence.length(); i++){
                if(sequence.charAt(i)==sequenceBuilder.charAt(i-1)){
                    cost++;
                    char one = sequence.charAt(i);
                     String optOne = options.replace(one+"", "");
                 
                    if(i<sequence.length()-1){
                        char two = sequence.charAt(i+1);
                        optOne = optOne.replace(two+"", "");
                        
                    }
                    sequenceBuilder.append(optOne.charAt(0));
                }
                else {
                    sequenceBuilder.append(sequence.charAt(i));
                }
            }
            System.out.println(cost);
            System.out.println(sequenceBuilder.toString());
        }
    }


    // This is a DP solution, however it runs in num*colors^2 which is too slow
    // for large numbers. The solution has been optimized for memory using
    // only a 2xnum size array. The slowdown probably comes from string
    // concatination which is O(n).
    public void solveDP () {
        Scanner s = new Scanner(System.in);
        // int lines = s.nextInt();
        int num = s.nextInt();
        int colors = s.nextInt();
        int[][] dp = new int[2][colors];
        StringBuilder[][] coloring = new StringBuilder[2][colors];
        String curPainting = s.next();
        int sub = (int) ('A');
        char curLetter = curPainting.charAt(0);
        for (int i = 0; i < colors; i++) {
            dp[0][i] = 1;
            coloring[0][i] = new StringBuilder();
            coloring[0][i].append((char) (sub + i));
            coloring[1][i] = new StringBuilder();
        }
        dp[0][(int) curLetter - sub] = 0;

        int roundMinCol = (int) curLetter - sub;
        int roundMin = 0;
        for (int pos = 1; pos < num; pos++) {
            char curColor = curPainting.charAt(pos);
            int storeAt = pos % 2;
            int lookAt = (pos - 1) % 2;

            int oldRoundMinCol = roundMinCol;
            int oldRoundMin = roundMin;
            roundMinCol = 0;
            roundMin = Integer.MAX_VALUE;

            for (int col = 0; col < colors; col++) {
                int min = Integer.MAX_VALUE;
                int index = 0;
                if (oldRoundMinCol == col) {
                    for (int colP = 0; colP < colors; colP++) {
                        if (colP != col) {

                            if (dp[lookAt][colP] < min) {
                                min = dp[lookAt][colP];
                                index = colP;
                            }
                        }
                    }
                }
                else {
                    min = oldRoundMin;
                    index = oldRoundMinCol;
                }
                int cost = 0;
                if ((curColor - sub) != col) {
                    cost = 1;
                }
                dp[storeAt][col] = min + cost;

                coloring[storeAt][col] = new StringBuilder(coloring[lookAt][index].toString());
                // System.out.println(coloring[storeAt][col].toString() +" "
                // +lookAt);
                coloring[storeAt][col].append((char) (col + sub));
                // System.out.println( coloring[storeAt][col].toString());
                if (dp[storeAt][col] < roundMin) {
                    roundMin = dp[storeAt][col];
                    roundMinCol = col;
                }

            }
        }
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int col = 0; col < colors; col++) {
            if (dp[(num - 1) % 2][col] < min) {
                min = dp[(num - 1) % 2][col];
                index = col;
            }
        }
        String acceptable = coloring[(num - 1) % 2][index].toString();
        System.out.println(min);
        System.out.println(acceptable);

    }

}