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

public class ColorStripe {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        String S = sc.next();
        
        if (K > 2) {
	        String aug = S + " ";
	        int chng = 0;
	        char[] arr = aug.toCharArray();
	        for (int i = 1; i < N; i++) {
	        	if (arr[i] == arr[i - 1]) {
	        		char c = firstBesides(arr[i - 1], arr[i + 1]);
	        		arr[i] = c;
	        		chng++;
	        	}
	        }
	        
	        String temp = new String(arr);
	        String output = temp.substring(0, N);
	        System.out.println(chng);
	        System.out.println(output);
        } else {
        	char[] arr = S.toCharArray();
        	int ch1 = 0;
        	int ch2 = 0;
        	for (int i = 0; i < arr.length; i++) {
        		if ((i % 2 == 0 && arr[i] == 'B') || (i % 2 == 1 && arr[i] == 'A')) {
        			ch1++;
        		} else if ((i % 2 == 0 && arr[i] == 'A') || (i % 2 == 1 && arr[i] == 'B')) {
        			ch2++;
        		}
        	}
        	int best = Math.min(ch1, ch2);
        	if (ch1 < ch2) {
        		for (int i = 0; i < arr.length; i++) {
        			if (i % 2 == 0) {
        				arr[i] = 'A';
        			} else {
        				arr[i] = 'B';
        			}
        		}
        	} else {
        		for (int i = 0; i < arr.length; i++) {
        			if (i % 2 == 0) {
        				arr[i] = 'B';
        			} else {
        				arr[i] = 'A';
        			}
        		}
        	}
        	String output = new String(arr);
        	System.out.println(best);
        	System.out.println(output);
        }
    }
    
    public static char firstBesides(char c1, char c2) {
    	for (char c = 'A'; c <= 'Z'; c++) {
    		if (c != c1 && c != c2) {
    			return c;
    		}
    	}
    	return 0;
    }

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            String str = "";
            try { str = br.readLine(); }
            catch (IOException e) { e.printStackTrace(); }
            return str;
        }
    }
}