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:
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;


public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc=new Scanner(System.in);
		StringBuilder sb=new StringBuilder();
	    int n=sc.nextInt();
	    int k=sc.nextInt();
	    String str=sc.next();
	    char s[]=str.toCharArray();
	    int c=0;
	    if(k==2)
	    {
	        char s1[]=new char[n];
	        char s2[]=new char[n];
	        StringBuilder sb1=new StringBuilder();
	        StringBuilder sb2=new StringBuilder();
	        for( int i=0;i<n;i++)
	        {
	            if(i%2==0)
	            {
	                s1[i]='A';
	                s2[i]='B';
	            }
	            else
	            {
	                s1[i]='B';
	                s2[i]='A';
	            }
	        }
	        int ch1=0;
	        int ch2=0;
	        for( int i=0;i<n;i++)
	        {
	            if(s1[i]!=s[i])
	            ch1++;
	            if(s2[i]!=s[i])
	            ch2++;
	            sb1.append(s1[i]);
	            sb2.append(s2[i]);
	        }
	        if(ch2<ch1)
	        {
	            System.out.println(ch2);
	            System.out.println(sb2.toString());
	        }
	        else
	        {
	            System.out.println(ch1);
	            System.out.println(sb1.toString());
	        }
	    }
	    else{
	    for( int i=1;i<n;i++)
	    {
	        if(s[i]==s[i-1])
	        {
	            s[i]='A';
	            c++;
	            while(s[i]==s[i-1]||(i+1<n&&s[i]==s[i+1]))
	            {
	                s[i]++;
	                
	            }
	            
	        }
	    }
	    System.out.println(c);
	    for( int i=0;i<n;i++)
	    {
	        sb.append(s[i]);
	    }
	    System.out.println(sb.toString());}
	}
}
class Pair{
    long x; int y;
    Pair( long x, int y)
    {
        this.x=x;
        this.y=y;
    }
}
class myComparator implements Comparator<Pair>
{
    public int compare(Pair a, Pair b)
    {
        return Integer.compare(a.y, b.y);
    }
}