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.InputStreamReader;
import java.util.ArrayList;


public class C135 {
    static int k;
    
    static char getOther(char f, char s, char cc){
        if(k==3 && f!=s && s!=cc && f!=cc && f!=' '&&s!=' ')return f;
        for(char c='A'; c<=(char)('A'+k-1);++c){
            if(c!=f && c!=s && c!=cc)return c;
        }
        return ' ';
    }
    
    
    
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] data = br.readLine().split(" ");
        
        int n = Integer.parseInt(data[0]);
        k = Integer.parseInt(data[1]);
        
        String str = br.readLine();
        char s[] = str.toCharArray();
        
        int c=0;
        if(k==2){
            int t=0;
            char beg = 'A';
            char tt[] = new char[s.length];
            char qq[] = new char[s.length];
            for(int i=0;i<s.length;++i){
                if(s[i]!=beg)t++;
                tt[i]=beg;
                beg = (beg=='A')?'B':'A';
            }
            int q=0;
            beg = 'B';
            for(int i=0;i<s.length;++i){
                if(s[i]!=beg)q++;
                qq[i]=beg;
                beg = (beg=='A')?'B':'A';
            }
            if(t<q){c=t;s=tt;}else {c=q;s=qq;}
            
        }else {
            for(int i=0;i<s.length;++i){
                int j=i;
                ArrayList<Integer> ind = new ArrayList<>();
                while(j+1<s.length && (s[j+1] == s[i])){
                    j++;
                    if((j-i)%2==1)ind.add(j);
                }
                if(j==i)continue;
                char prev;
                if(i-1==-1)prev=' ';
                else prev = s[i-1];
                char next =' ';
                if(j+1<s.length)next = s[j+1];
                char curr = s[i];
                //System.out.println(new String(s));
                //System.out.println("prev = "+prev+" next = "+next+" curr = "+curr);
                char other = getOther(prev, next, curr);
                for(int kk:ind)s[kk] = other;
                c+=ind.size();
            }
        }
        System.out.println(c+"\n"+new String(s));
    }
}