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:
/**
 * Created by Alex on 8/4/2014.
 */

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

public class Solution {

    public void solve() throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();

        char[] s = new char[n + 5];
        String str = in.readLine();

        for (int i = 0; i < n; i++)
            s[i] = str.charAt(i);

        if (k > 2) {
            int ans = 0;
            for (int i = 0; i < n; i++)
                if (s[i] == s[i + 1]) {
                    ans++;
                    s[i + 1] = 'A';
                    while (s[i] == s[i + 1] || s[i + 1] == s[i + 2])
                        s[i + 1]++;
                }

            out.println(ans);
            for (int i = 0; i < n; i++)
                out.print(s[i]);
            out.println();
        } else {
            int cnt = 0;
            for (int i = 1; i < n; i++) {
                if (s[i] != s[i - 1])
                    continue;

                cnt++;

                if (s[i] == 'B')
                    s[i] = 'A';
                else
                    s[i] = 'B';
            }

            int ans = cnt;

            if (n - cnt < ans) {
                ans = n - cnt;

                for (int i = 0; i < n; i++)
                    if (s[i] == 'B')
                        s[i] = 'A';
                    else
                        s[i] = 'B';
            }

            out.println(ans);
            for (int i = 0; i < n; i++)
                out.print(s[i]);
            out.println();
        }

    }

    private FastScanner in;
    private PrintWriter out;

    public void run() {
        try {
//            in = new FastScanner(new File(".in"));
//            out = new PrintWriter(new File(".out"));
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            in = new FastScanner(inputStream);
            out = new PrintWriter(outputStream);
            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class FastScanner extends BufferedReader {
        StringTokenizer st = null;

        FastScanner(File f) throws FileNotFoundException {
            super(new FileReader(f));
        }

        FastScanner(InputStream is) {
            super(new InputStreamReader(is));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(super.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

    }

    public static void main(String[] arg) {
        new Solution().run();
    }
}