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:
//https://codeforces.com/problemset/problem/219/C
//package codeforces_219;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class C1 {

    private static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int nextInt () {
            return Integer.parseInt(next());
        }
    }

    private static final FastScanner scanner = new FastScanner();

    private static class Input {
        int n, k;
        char[] cells;

        public Input() {
            n = scanner.nextInt();
            k = scanner.nextInt();
            cells = scanner.next().toCharArray();
        }

        public String toString() {
            return n + " " + k + "\n" + new String(cells);
        }
    }

    public static void main(String[] args) {
        Input input = new Input();
        if (input.k == 2) process2LetterInput(input);
        else process(input);
    }

    private static void process(Input input) {
        int ans = 0;
        char[] res = new char[input.n];
        res[0] = input.cells[0];
        for (int i = 1; i < input.n; i++) {
            if (input.cells[i] == res[i-1]) {
                ans++;
                boolean isAUsed = false;
                boolean isBUsed = false;
                if (input.cells[i] == 'A') isAUsed = true;
                if (input.cells[i] == 'B') isBUsed = true;

                if (i < input.n-1) {
                    if (input.cells[i+1] == 'A') isAUsed = true;
                    if (input.cells[i+1] == 'B') isBUsed = true;
                }
                if (isAUsed) {
                    if (isBUsed) {
                        res[i] = 'C';
                    } else {
                        res[i] = 'B';
                    }
                } else {
                    res[i] = 'A';
                }
            } else {
                res[i] = input.cells[i];
            }
        }
        System.out.println(ans);
        System.out.println(new String(res));
    }

    private static void process2LetterInput(Input input) {
        char[] startWithA = new char[input.n];
        char[] startWithB = new char[input.n];

        startWithA[0] = 'A';
        startWithB[0] = 'B';

        for (int i = 1; i < input.n; i++) {
            if ('A' == startWithA[i-1]) {
                startWithA[i] = 'B';
                startWithB[i] = 'A';
            } else {
                startWithA[i] = 'A';
                startWithB[i] = 'B';
            }
        }

        int compareWithAStart = compare(startWithA, input.cells);
        int compareWithBStart = compare(startWithB, input.cells);

        if (compareWithAStart <= compareWithBStart) {
            System.out.println(compareWithAStart);
            System.out.println(new String(startWithA));
        } else {
            System.out.println(compareWithBStart);
            System.out.println(new String(startWithB));
        }
    }

    private static int compare(char[] s1, char[] s2) {
        int res = 0;
        for (int i = 0; i < s1.length; i++) {
            if (s1[i] != s2[i]) res++;
        }
        return res;
    }
}