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

    public class Main implements Runnable 
    {
        static class InputReader 
        {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
            private SpaceCharFilter filter;
            private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            public InputReader(InputStream stream) 
            {
                this.stream = stream;
            }
            
            public int read()
            {
                if (numChars==-1) 
                    throw new InputMismatchException();
                
                if (curChar >= numChars) 
                {
                    curChar = 0;
                    try
                    {
                        numChars = stream.read(buf);
                    }
                    catch (IOException e)
                    {
                        throw new InputMismatchException();
                    }
                    
                    if(numChars <= 0)               
                        return -1;
                }
                return buf[curChar++];
            }
        
            public String nextLine()
            {
                String str = "";
                try
                {
                    str = br.readLine();
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }    
                return str;
            }
            public int nextInt() 
            {
                int c = read();
                
                while(isSpaceChar(c)) 
                    c = read();
            
                int sgn = 1;
            
                if (c == '-') 
                {
                    sgn = -1;
                    c = read();
                }
                
                int res = 0;
                do
                {
                    if(c<'0'||c>'9') 
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                while (!isSpaceChar(c)); 
            
                return res * sgn;
            }
            
            public long nextLong() 
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                long res = 0;
                
                do 
                {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }    
                while (!isSpaceChar(c));
                    return res * sgn;
            }
            
            public double nextDouble() 
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                int sgn = 1;
                if (c == '-')
                {
                    sgn = -1;
                    c = read();
                }
                double res = 0;
                while (!isSpaceChar(c) && c != '.') 
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                }
                if (c == '.') 
                {
                    c = read();
                    double m = 1;
                    while (!isSpaceChar(c))
                    {
                        if (c == 'e' || c == 'E')
                            return res * Math.pow(10, nextInt());
                        if (c < '0' || c > '9')
                            throw new InputMismatchException();
                        m /= 10;
                        res += (c - '0') * m;
                        c = read();
                    }
                }
                return res * sgn;
            }
        
            public String readString() 
            {
                int c = read();
                while (isSpaceChar(c))
                    c = read();
                StringBuilder res = new StringBuilder();
                do 
                {
                    res.appendCodePoint(c);
                    c = read();
                } 
                while (!isSpaceChar(c));
                
                return res.toString();
            }
        
            public boolean isSpaceChar(int c) 
            {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
        
            public String next()
            {
                return readString();
            }
            
            public interface SpaceCharFilter
            {
                public boolean isSpaceChar(int ch);
            }
        }
        public static void main(String args[]) throws Exception 
        {
            new Thread(null, new Main(),"Main",1<<27).start();
        }
        
        static class Pair{
            int f;
            int s;
            
            
            Pair(int f,int s){
                this.f=f;
                this.s=s;
                
            }
            
            public static Comparator<Pair> wc = new Comparator<Pair>(){
                public int compare(Pair e1,Pair e2){
                    
                    //reverse order
                    if(e1.s < e2.s) 
                        return 1;  // 1 for swaping.
                    else if (e1.s > e2.s) 
                        return -1; 
                    else {
                        //System.out.println("* "+e1.nod+" "+e2.nod);
                        return 0;
                    } 
                    
                }
            };	
        }

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


        ////recursive BFS
        public static int bfsr(int s,ArrayList<Integer>[] a,boolean[] b,int[] pre){
            b[s]=true;
            int p = 1;
            int n = pre.length -1;
            int t = a[s].size();
            int max = 1;
            for(int i=0;i<t;i++){
                int x = a[s].get(i);
                if(!b[x]){
                    //dist[x] = dist[s] + 1;
                    int xz =  (bfsr(x,a,b,pre));
                    p+=xz;
                    max = Math.max(xz,max);
                }
            }
            max = Math.max(max,(n-p));
            pre[s] = max;
            return p;
        }

    //// iterative BFS
        public static int bfs(int s,ArrayList<Integer>[] a,int[] dist,boolean[] b,PrintWriter w){
            b[s]=true;
            int siz = 0;
            
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            while(q.size()!=0){
                int i=q.poll();
                Iterator<Integer> it = a[i].listIterator();
                int z=0;
                while(it.hasNext()){
                    z=it.next();
                    if(!b[z]){
                        b[z]=true;
                        dist[z] = dist[i] + 1;
                        siz++;
                        q.add(z);
                    }
                }   
            
            }
            return siz;
        }

        public static int lower(int key, int[] a){
            int l = 0;
            int r = a.length-1;
            int res = 0;

            while(l<=r){
                int mid = (l+r)/2;

                if(a[mid]<=key){
                    l = mid+1;
                    res = mid+1;
                }
                else{
                    r = mid -1;
                }
            }

            return res;
        }

        


    //////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////


        public void run()
        {
            InputReader sc = new InputReader(System.in);
            PrintWriter w = new PrintWriter(System.out);
            long defaultValue=0;
            

            
            // int tc = sc.nextInt();
            // while(tc-->0){
                int n = sc.nextInt();
                int k = sc.nextInt();
                char[] a = sc.next().toCharArray(); 
                int ans = 0;
                if(k>2){
                    int c = 1;
                    int i=1;
                    for(i=1;i<n;i++){
                        if(a[i]==a[i-1]){
                            c++;
                        }
                        else{
                            if(c>1){
                                for(int j=i-1;c>1;c--){
                                    if(c%2==0){
                                        if(j!=n-1){
                                            if(a[j+1]!='A' && a[j-1]!='A')a[j] = 'A';
                                            else if(a[j+1]!='B' && a[j-1]!='B')a[j] = 'B';
                                            else a[j] = 'C';
                                        }
                                        else{
                                            if( a[j-1]!='A')a[j] = 'A';
                                            else if(a[j-1]!='B')a[j] = 'B';
                                            else a[j] = 'C';
                                        }
                                        ans++;
                                    }
                                    j--;
                                }
                            }
                            c = 1;
                        }
                    }
                    if(c>1){
                        for(int j=i-1;c>1;c--){
                            if(c%2==0){
                                if(j!=n-1){
                                    if(a[j+1]!='A' && a[j-1]!='A')a[j] = 'A';
                                    else if(a[j+1]!='B' && a[j-1]!='B')a[j] = 'B';
                                    else a[j] = 'C';
                                }
                                else{
                                    if( a[j-1]!='A')a[j] = 'A';
                                    else if(a[j-1]!='B')a[j] = 'B';
                                    else a[j] = 'C';
                                }
                                ans++;
                            }
                            j--;
                        }
                    }

                }
                else{
                    for(int i=0;i<n;i++){
                        if((a[i]-65)!=(i%2))ans++;
                    }
                    if(ans>(n/2)){
                        ans = n-ans;
                        for(int i=0;i<n;i++){
                            if((i%2)==0) a[i] = 'B';
                            else a[i] = 'A';
                        }
                    }
                    else{
                        for(int i=0;i<n;i++){
                            if((i%2)==0) a[i] = 'A';
                            else a[i] = 'B';
                        }
                    }
                }
                w.println(ans);
                for(int i=0;i<n;i++){
                    w.print(a[i]);
                }






            //}
            w.flush();
            w.close();
        }
        
    
        

        
    }