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 static java.lang.Math.*;
import static java.util.Arrays.*;

public class ladders219c {
    static BufferedReader __in;
    static PrintWriter __out;
    static StringTokenizer input;

    public static void main(String[] args) throws IOException {
        __in = new BufferedReader(new InputStreamReader(System.in));
        __out = new PrintWriter(new OutputStreamWriter(System.out));

        read();
        int n = nextInt(), k = nextInt();
        char[] str = readLine().toCharArray();
        if(k == 2) {
           int acnt = 0, bcnt = 0;
           char[] a = new char[n], b = new char[n];
           for(int i = 0; i < n; ++i) {
               acnt += str[i] == (b[i] = (i % 2 == 0 ? 'A' : 'B')) ? 1 : 0;
               bcnt += str[i] == (a[i] = (i % 2 == 1 ? 'A' : 'B')) ? 1 : 0;
           }
           if(acnt < bcnt) {
               println(acnt);
               println(new String(a));
           } else {
               println(bcnt);
               println(new String(b));
           }
        } else {
            int cnt = 0, strk = 0;
            for(int i = 0; i < n - 1; ++i) {
                if(str[i] == str[i + 1]) {
                    if(++strk % 2 == 1) {
                        ++cnt;
                        str[i + 1] = 'A';
                        while(str[i] == str[i + 1] || !(i == n - 2) && str[i + 1] == str[i + 2]) {
                            ++str[i + 1];
                        }
                    }
                } else {
                    strk = 0;
                }
            }
            println(cnt);
            println(new String(str));
        }

        close();
    }

    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final long LMAX = 9223372036854775807L;
    static void read() throws IOException {input = new StringTokenizer(__in.readLine());}
    static String readLine() throws IOException {return __in.readLine();}
    static int nextInt() {return Integer.parseInt(input.nextToken());}
    static int readInt() throws IOException {return Integer.parseInt(__in.readLine());}
    static void print(String s) {__out.print(s);}
    static void println(String s) {__out.println(s);}
    static void print(Object o) {__out.print(o);}
    static void println(Object o) {__out.println(o);}
    static void printy() {__out.println("Yes");}
    static void printY() {__out.println("YES");}
    static void printn() {__out.println("No");}
    static void printN() {__out.println("NO");}
    static void printyn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void printYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void println(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), i++); __out.println(a[a.length - 1]);}
    static void println() {__out.println();}
    static void close() {__out.close();}
}