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

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().run(in, out);
        out.close();
    }


    int N, K;
    char[] ca;
    int[] cc;

    void run(FastScanner in, PrintWriter out) {
        N = in.nextInt();
        K = in.nextInt();
        if (K == 2) {
            run2(in, out);
            return;
        }
        ca = in.next().toCharArray();

        int cnt = 0;
        for (int i = 0; i < N; i++) {
            char c = ca[i];
            if (i != 0 && c == ca[i-1]) {
                cnt++;
                if (i == N-1) {
                    c = ca[i-1] == 'A' ? 'B' : 'A';
                } else {
                    c = 'A';
                    if (ca[i-1] == 'A' || ca[i+1] == 'A') c++;
                    if (c == 'B' && (ca[i-1] == 'B' || ca[i+1] == 'B')) c++;
                }
            }
            ca[i] = c;
        }
        out.println(cnt);
        out.println(new String(ca));

    }

    void run2(FastScanner in, PrintWriter out) {
        ca = in.next().toCharArray();
        cc = new int[N];
        for (int i = 0; i < ca.length; i++) cc[i] = ca[i]-'A';

        int[][] dp = new int[N][K];
        // base
        for (int i = 0; i < K; i++) {
            dp[0][i] = (cc[0] == i) ? 0 : 1;
        }

        for (int i = 1; i < N; i++) {

            final int I = i;
            TreeSet<Integer> ts = new TreeSet<>((a, b) -> {
                if (dp[I-1][a] != dp[I-1][b]) return dp[I-1][a]-dp[I-1][b];
                return a-b;
            });
            for (int k = 0; k < K; k++) ts.add(k);


            for (int k = 0; k < K; k++) {
                ts.remove(k);
                dp[i][k] = dp[i-1][ts.first()] + (cc[i] == k ? 0 : 1);
                ts.add(k);
            }
        }

        int min = Integer.MAX_VALUE;

        for (int k = 0; k < K; k++) {
            if (dp[N-1][k] < min) {
                min = dp[N-1][k];
            }
        }

        out.println(min);
        LinkedList<Character> l = new LinkedList<>();
        int prev = -1;
        for (int i = N-1; i >= 0; i--) {
            for (int k = 0; k < K; k++) {
                if (i == N-1) {
                    if (dp[i][k] == min) {
                        l.offerFirst((char) ('A'+k));
                        prev = k;
                        break;
                    }
                    continue;
                }

                // can move
                // if the cost is the same
                // if the cost is one more
                if ((dp[i][k] == min && prev == cc[i+1] && k != prev)
                        || (dp[i][k]+1 == min && prev != cc[i+1] && k != prev)) {
                    l.offerFirst((char) ('A'+k));
                    prev = k;
                    min = dp[i][k];
                    break;
                }
            }
        }

        for (char c : l) out.print(c);
        out.println();

    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }

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

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

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