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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
     
    public class B {
  
    	static int n, k;
    	static char[] a;
    	public static void main(String[] args) throws IOException{
     
    		Scanner sc = new Scanner(System.in);
    		PrintWriter out = new PrintWriter(System.out);
    		n = sc.nextInt(); k = sc.nextInt();
    		String in = sc.next();
    		a = in.toCharArray();
    		int ans = 0;
    		if(k == 2)
    		{
    			int c1 = countChanges('A', 'B');
    			int c2 = countChanges('B', 'A');
    			if(c1 < c2)
    				fillAB('A', 'B');
    			else
    				fillAB('B', 'A');
    			ans = Math.min(c1, c2);
    		}
    		else
	    		for(int i = 0; i < n-1; i++)
	    			if(a[i] == a[i+1])
	    			{
	    				ans++;
	    				a[i+1] = i == n-2? chooseColor(a[i], '#') : chooseColor(a[i], a[i+2]);
	    			}
    		out.println(ans);
    		for(int i = 0; i < n; i++)
    			out.print(a[i]);
    		out.println();
    		out.flush();
    	}
    	
    	static char chooseColor(char c1, char c2)
    	{
    		for(char c = 'A'; c < k+'A'; c++)
    			if(c != c1 && c != c2)
    				return c;
    		return '0';
    	}
    	
    	static int countChanges(char c1, char c2)
    	{
    		int c = 0;
			char cur;
			for(int i = 0; i < n; i++)
			{
				if(i % 2 == 0) cur = c1;
				else cur = c2;
				if(a[i] != cur) c++;
			}
			return c;
    	}
    	
    	static void fillAB(char c1, char c2)
    	{
    		for(int i = 0; i < n; i++)
				if(i % 2 == 0) a[i] = c1;
				else a[i] = c2;
    	}
    	
    	static class Scanner 
    	{
    		StringTokenizer st;
    		BufferedReader br;
     
    		public Scanner(InputStream System){	br = new BufferedReader(new InputStreamReader(System));	}
    		public String next() throws IOException 
    		{
    			while (st == null || !st.hasMoreTokens()) 
    				st = new StringTokenizer(br.readLine());
    			return st.nextToken();
    		}
    		public String nextLine()throws IOException{return br.readLine();}
    		public int nextInt() throws IOException {return Integer.parseInt(next());}
    		public double nextDouble() throws IOException {return Double.parseDouble(next());}
    		public char nextChar()throws IOException{return next().charAt(0);}
    		public Long nextLong()throws IOException{return Long.parseLong(next());}
    		public boolean ready() throws IOException{return br.ready();}
    		public void waitForInput(){for(long i = 0; i < 3e9; i++);}
    	}
    }