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.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ProblemC {
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] line = s.readLine().split(" ");
        int n = Integer.valueOf(line[0]);
        int k = Integer.valueOf(line[1]);
        
        String q = s.readLine();
        int[] a = new int[n];
        for (int i = 0 ; i < n ; i++) {
            a[i] = q.charAt(i) - 'A';
        }
        
        int[][][] another = new int[k][k][k];
        for (int i = 0 ; i < k ; i++) {
            for (int j = 0 ; j < k ; j++) {
                for (int l = 0 ; l < k ; l++) {
                    for (int m = 0 ; m < k ; m++) {
                        if (m != i && m != j && m != l) {
                            another[i][j][l] = m;
                        }
                    }
                }
            }
        }
        
        
        int[] dp = new int[27];
        int[] dp_next = new int[27];
        int[][] dp_prev = new int[n+1][27];
        for (int i = 0 ; i <= n ; i++) {
            Arrays.fill(dp_prev[i], -1);
        }
        Arrays.fill(dp_next, Integer.MAX_VALUE);
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[26] = 0;
        
        for (int i = 0 ; i < n ; i++) {
            for (int j = 0 ; j <= 26 ; j++) {
                if (dp[j] == Integer.MAX_VALUE) {
                    continue;
                }
                
                int prev = (j == 26) ? a[i] : j;
                int next = (i == n-1) ? a[i] : a[i+1];
                int now = a[i];
                
                int[] narr = {a[i], another[prev][now][next], another[prev][now][now]};
                for (int ner = 0 ; ner < narr.length ; ner++) {
                    int ne = narr[ner];
                    if (j == ne) {
                        continue;
                    }
                    int nv = dp[j] + ((a[i] == ne) ? 0 : 1);
                    if (dp_next[ne] > nv) {
                        dp_next[ne] = nv;
                        dp_prev[i+1][ne] = j;
                    }
                }
            }
            for (int j = 0 ; j <= 26 ; j++) {
                dp[j] = dp_next[j];
                dp_next[j] = Integer.MAX_VALUE;
            }
        }
        
        int minval = Integer.MAX_VALUE;
        int finchar = 0;
        for (int i = 0 ; i < 26 ; i++) {
            if (minval > dp[i]) {
                minval = dp[i];
                finchar = i;
            }
        }
        
        
        char[] minbuffer = new char[n];
        int now_n = n;
        int now_p = finchar;
        while (now_n >= 1) {
            minbuffer[now_n-1] = (char)('A' + now_p);
            now_p = dp_prev[now_n][now_p];
            now_n--;
        }
        
        System.out.println(minval);
        System.out.println(String.valueOf(minbuffer));
    }
}