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.io.ObjectInputStream.GetField;
import java.util.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	public void solve () throws Exception {
		int n = nextInt();
		int k = nextInt();
		
		char s [] = in.readLine().toCharArray();
		
		int t [] = new int [n];
		for (int i = 0; i < n; i++) {
			t [i] = s[i] - 'A';
		}
		
		int d [][] = new int [n][k];
		int pre [][] = new int [n][k];
		
		for (int i = 0; i < k; i++) {
			if (i == t[0]) {
				d[0][i] = 0;
			} else {
				d[0][i] = 1;
			}
		}
		
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < k; j++) {
				d[i][j] = Integer.MAX_VALUE / 2;
			}
		}
		
		for (int i = 1; i < n; i++) {
			for (int last = 0; last < k; last++) {
				if (d[i - 1][last] == Integer.MAX_VALUE / 2) continue;
				for (int j = t[i] - 3; j <= t[i] + 3; j++) {
					if (j >= 0 && j < k && j != last) {
						int modify = (j == t[i]) ? 0 : 1;
						if (d[i][j] > d[i - 1][last] + modify) {
							d[i][j] = d[i - 1][last] + modify;
							pre [i][j] = last;
						}
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		int result = Integer.MAX_VALUE / 2;
		int last = -1;
		for (int j = 0; j < k; j++) {
			if (d[n - 1][j] < result) {
				result = d[n - 1][j];
				last = j;
			}
		}
		sb.append((char)(last + 'A'));
		int i = n - 1;
		while (i != 0) {
			sb.append((char)(pre[i][last] + 'A'));
			last = pre[i][last];
			i--;
		}
		out.println(result);
		out.println(sb.reverse().toString());
		
	}
	
	private static final String fname = "";
	private static long stime = 0;
	
	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;
	
	private String nextToken () throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}
	
	private int nextInt () throws Exception {
		return Integer.parseInt(nextToken());
	}
	
	private long nextLong () throws Exception {
		return Long.parseLong(nextToken());
	}
	
	private double nextDouble () throws Exception {
		return Double.parseDouble(nextToken());
	}
	
	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve ();
		} catch (Exception e) {
			throw new RuntimeException(e);
		} finally {
			out.close();
		}
	}
	
	public static void main(String[] args) {
		new Thread(null, new Solution(), "", 1<<26).start();
	}

}