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.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
 
public class Main
{
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                solve();
            }
        }, "1", 1 << 26).start();
    }
    static void solve () {
        FastReader fr =new FastReader();    PrintWriter op =new PrintWriter(System.out);
 
        int n =fr.nextInt() ,k =fr.nextInt() ,a[] =new int[n+1] ,i ,j ,l ,ct ;  String s =fr.next() ;
        for (i =0 ; i<n ; ++i)  a[i] =s.charAt(i)-64 ;  a[n] =ct =0 ;
 
        if (k>2) {
            for (i =1 ; i<n ; i++) {
                if (a[i]!=a[i-1])   continue ;  ++ct ;
                for (j =1 ; j<=k ; ++j) {
                    if (a[i+1]!=j && a[i]!=j)   break;
                }
                a[i] =j ;
            }
        }
        else {
            j =0 ;  l =ct =0 ;
            for (i =0 ; i<n ; ++i) {
                if (a[i]!=(j+1))    ++l ;
                j =(j+1)%2 ;
            }
            j =1 ;
            for (i =0 ; i<n ; ++i) {
                if (a[i]!=(j+1))    ++ct ;
                j =(j+1)%2 ;
            }
            if (ct<l) j =1 ;    else    {   ct =l ; j =0 ;  }
            for (i =0 ; i<n ; ++i) {
                a[i] =j+1 ; j =(j+1)%2 ; 
            }
        }
        op.println(ct) ;
        for (i =0 ; i<n ; ++i)  op.print((char)(a[i]+64)) ;
        op.flush();    op.close();
    }
    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();
        }
 
        String nextLine() {
            String str ="";
 
            try
            {
                str =br.readLine();
            }
            catch(IOException e)
            {
                e.printStackTrace();
            }
 
            return str;
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next()) ;
        }
    }
}