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.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.FileReader;
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.File;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author monsterspy
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        Output out = new Output(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, FastScanner s, Output ww) {
        try {
            int n = s.nextInt();
            int k = s.nextInt();
            char[] c = s.nextString().toCharArray();
            if(k == 2){
                StringBuilder ss = process2(c);
                ww.print(cnt+"\n");
                ww.print(ss);
            }
            else{
                StringBuilder ss = processO(c);
                ww.print(cnt+"\n");
                ww.print(ss);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    int cnt = 0;
    public StringBuilder processO(char[] a){
        int len = a.length;
        StringBuilder str = new StringBuilder("");
        for(int i=0;i<len;i++){
            char b = 0;
            char aa = 0;
            if(i!=0) aa = a[i-1];
            if(i+1 != len) b = a[i+1];
            if(aa == a[i]){
                char ch = 'A';
                if(aa == ch || b == ch)
                    ch++;
                if(aa == ch || b == ch)
                    ch++;
                str.append(ch);
                a[i] = ch;
                cnt++;
            }else str.append(a[i]);

        }
        return str;

    }

    public StringBuilder process2(char[] c){
        int len = c.length;
        int one = 0;
        int two = 0;
        for(int i=0;i<len;i+=2){
            if(c[i] != 'A') one++;
            if(c[i] != 'B') two++;
        }
        for(int i=1;i<len;i+=2){
            if(c[i] != 'B') one++;
            if(c[i] != 'A') two++;
        }
        int min = Math.min(one,two);
        StringBuilder str = new StringBuilder("");
        if(min == one){
            for(int i=0;i<len;i++){
                if(i % 2 == 0) str.append('A');
                else str.append('B');
            }
        }else{
            for(int i=0;i<len;i++){
                if(i % 2 == 0) str.append('B');
                else str.append('A');
            }
        }
        cnt = min;
        return str;
    }
}

class FastScanner {
    BufferedReader s;
    StringTokenizer st;

    public FastScanner(InputStream InputStream){
        st = new StringTokenizer("");
        s = new BufferedReader(new InputStreamReader(InputStream));
    }

    public FastScanner(File f) throws FileNotFoundException{
        st = new StringTokenizer("");
        s = new BufferedReader (new FileReader(f));
    }

    public int nextInt() throws IOException{
        if(st.hasMoreTokens())
            return Integer.parseInt(st.nextToken());
        else{
            st = new StringTokenizer(s.readLine());
            return nextInt();
        }
    }

    public String nextString() throws IOException{
        if(st.hasMoreTokens())
            return st.nextToken();
        else{
            st = new StringTokenizer(s.readLine());
            return nextString();
        }

    }

}

class Output {

    private final PrintWriter writer;

    public Output(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public Output(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void close() {
        writer.close();
    }


}