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.lang.*;
import java.util.*;
import java.math.*;

public class code
{
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
  
	public static void main(String args[])throws IOException
	{
		FastReader scn = new FastReader();

		int n = scn.nextInt();
		int k = scn.nextInt();
		String input = scn.nextLine();
		if(k==2)
		{
			char start = 'B';
			int cost1 = 0;
			StringBuilder out1 = new StringBuilder();
			for(int i = 0; i < n; i++)
			{
				cost1 = cost1 + ((input.charAt(i)==start)?0:1);
				out1.append(start);
				start = toggle(start);
			}

			start = 'A';
			int cost2 = 0;
			StringBuilder out2 = new StringBuilder();
			for(int i = 0; i < n; i++)
			{
				cost2 = cost2 + ((input.charAt(i)==start)?0:1);
				out2.append(start);
				start = toggle(start);
			}

			if(cost1 < cost2)
			{
				System.out.println(cost1);
				System.out.println(out1.toString());
			}
			else
			{
				System.out.println(cost2);
				System.out.println(out2.toString());
			}
			return;
		}


		StringBuilder output = new StringBuilder();
		output.append(input.charAt(0));
		int cost = 0;
		for(int i = 1; i < n; i++)
		{
	
			char left = output.charAt(i-1);
			char right = left;
			if(i!=n-1)
				right = input.charAt(i+1);
			if(input.charAt(i)!=left)
			{
				output.append(input.charAt(i));
				continue;
			}

			cost++;
			for(int j = 0; j < k; j++)
			{
				char t = (char)('A' + j);
				if(t!=left && t!=right)
				{
					output.append(t);
					break;
				}
			}
		}

		System.out.println(cost);
		System.out.println(output.toString());

	}

	public static char toggle(char x)
	{
		return (x=='A')?'B':'A';
	}

	public static long gcd(long a, long b)
	{
		if(a==0)
			return b;
		if(b==0)
			return a;

		if(a<b)
			return gcd(a, b%a);
		else
			return gcd(b, a%b);
	}
	public static boolean dfs(Node start, Node end)
	{
		if(start == end )
			return true;

		start.visited = true;
		for(Node n: start.neighbors)
		{
			if(n.visited)
				continue;

			boolean result = dfs(n, end);
			if(result)
				return result;		
		}

		return false;
	}


}


class Node
{
	long a, b;
	boolean visited;
	ArrayList<Node> neighbors;

	public Node(long a, long b)
	{
		this.a = a;
		this.b = b;
		neighbors = new ArrayList<>();
	}

	public void initNeighbors(ArrayList<Node> list)
	{
		for(Node n: list)
		{
			if((n.a < this.a && this.a < n.b) || (n.a < this.b && this.b < n.b))
			{
				this.neighbors.add(n);
			}
			if((this.a < n.a && n.a < this.b) || (this.a < n.b && n.b < this.b))
			{
				n.neighbors.add(this);
			}
		}
	}
}

class Pair implements Comparable<Pair>
{
	long a, b;
	public Pair(long a, long b)
	{
		this.a = a;
		this.b = b;	
	}

	public int compareTo(Pair p)
	{
		if(this.b < p.b)
			return -1;
		else if (this.b > p.b)
			return 1;
		else
			return 0;
	}
}