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.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Solution {
    //<editor-fold desc="input parse" defaultstate="collapsed">

    private static StringTokenizer st;
    private static BufferedReader reader;
    private static BufferedWriter writer;

    private static long nextLong() {
        return Long.parseLong(st.nextToken());
    }

    private static int nextInt() {
        return Integer.parseInt(st.nextToken());
    }

    private static double nextDouble() {
        return Double.parseDouble(st.nextToken());
    }

    private static short nextShort() {
        return Short.parseShort(st.nextToken());
    }

    private static byte nextByte() {
        return Byte.parseByte(st.nextToken());
    }

    private static void initTokenizer() throws Exception {
        st = new StringTokenizer(reader.readLine());
    }

    //</editor-fold>
    
    public static void main(String[] args) throws Exception {
	reader = new BufferedReader(new InputStreamReader(System.in));
	writer = new BufferedWriter(new OutputStreamWriter(System.out), 1 << 20);
	
	initTokenizer();
	
	int n = nextInt();
	int k = nextInt();
	
	char[] a = reader.readLine().trim().toCharArray();
	
	if (k == 2) {
	    int bestsum = Integer.MAX_VALUE;
	    int sum = 0;
	    boolean first = true;
	    
	    for (int i = 0; i < n; i++) {
		char c = ((i & 1) == 0 ? 'A' : 'B');
		if (c != a[i]) sum++;
	    }
	    
	    if (sum < bestsum) bestsum = sum;
	    
	    sum = 0;
	    for (int i = 0; i < n; i++) {
		char c = ((i & 1) != 0 ? 'A' : 'B');
		if (c != a[i]) sum++;
	    }
	    
	    if (sum < bestsum) {
		writer.write(String.valueOf(sum));
		writer.newLine();
		for (int i = 0; i < n; i++) writer.write((i & 1) != 0 ? 'A' : 'B');
		writer.close();
		return;
	    }
	    else {
		writer.write(String.valueOf(bestsum));
		writer.newLine();
		for (int i = 0; i < n; i++) writer.write((i & 1) == 0 ? 'A' : 'B');
		writer.close();
		return;
	    }
	}
	
	int count = 0;
	char c = ' ';
	
	int sum = 0;
	
	TreeSet<Character> set = new TreeSet<>();
	
	for (int i = 0; i < k; i++) {
	    set.add((char)('A' + i));
	}
	
	for (int i = 1; i < n; i++) {
	    if (a[i] == a[i - 1]) {
		if (i + 1 == n) {
		    set.remove(a[i - 1]);
		    a[i] = set.first();
		    set.add(a[i - 1]);
		}
		else {
		    set.remove(a[i - 1]);
		    set.remove(a[i + 1]);
		    a[i] = set.first();
		    set.add(a[i - 1]);
		    set.add(a[i + 1]);
		}
		sum++;
	    }
	}
	
	writer.write(String.valueOf(sum));
	writer.newLine();
	for (char ch : a) writer.write(ch);
	writer.close();
    }
}