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.util.*;

public class color_stripe 
{
	static int moves = 0;
	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
	
	void modify(char[]s, int i, int j, int k)
	{
		if ((j-i+1)%2==0)
		{
			int kf = -1;
			if (j+1<s.length)
			 kf = s[j+1]-'A';
			int kb = s[i]-'A';
			int lo = 0;
			for (;lo < k; lo++)
				{
				if (lo!=kf && lo!=kb)
					break;
				}
			char c = (char)(lo+'A');
			int hi = j;
			while (hi>=i)
			{
				s[hi] = c;
				moves++;
				hi = hi-2;
				
			}
		}
		else
		{
			int lo = 0;
			int kb = s[i]-'A';
			for (;lo < k; lo++)
			{
			if (lo!=kb)
				break;
			}
		char c = (char)(lo+'A');
		int hi = j-1;
		while (hi>=i)
		{
			s[hi] = c;
			moves++;
			hi = hi-2;
			
		}
		}
	}
	public static void main(String args[])throws IOException
	{
		InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader sc = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        color_stripe cs = new color_stripe();
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        char [] s = sc.next().toCharArray();
        
      
        int i = 0;
        if (k == 2)
        {
        	StringBuilder ans1 = new StringBuilder();
        	StringBuilder ans2 = new StringBuilder();
        	int moves1 = 0;
        	int moves2 = 0;
        	while (i< n)
        	{
        		if (s[i]!='A')
        			moves1++;
        		ans1 = ans1.append('A');
        		i++;
        		if (i>=n)
        			break;
        		if (s[i]!='B')
        			moves1++;
        		ans1 = ans1.append('B');
        		i++;
        	}
        	i = 0;
        	while (i< n)
        	{
        		if (s[i]!='B')
        			moves2++;
        		ans2 = ans2.append('B');
        		i++;
        		if (i>=n)
        			break;
        		if (s[i]!='A')
        			moves2++;
        		ans2 = ans2.append('A');
        		i++;
        	}
        	if (moves1<moves2)
        		{out.println(moves1); out.println(ans1);out.close(); out.flush(); return;}
        	else
        		{out.println(moves2); out.println(ans2);out.close(); out.flush(); return;}
        	
        }
        else
        {
        	i = 0;
        	while (i<n-1)
        	{
        		if (s[i]==s[i+1])
        		{
        			int j = i+1;
        			for (; j< n-1; j++)
        			{
        				if (s[j]!=s[j+1])
        					break;
        			}
        			//out.println(i+" "+j);
        			cs.modify(s, i, j, k);
        			i = j+1;
        			
        		}
        		else
        			i++;
        	}
            
        }
        
        out.println(moves);
        StringBuilder ans = new StringBuilder();
        for ( i = 0; i< s.length; i++)
        	ans.append(s[i]);
        out.println(ans.toString().trim());
        out.close();
        out.flush();
	}
}