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.util.StringTokenizer;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;

    void solve() throws IOException {
        int n = nextInt();
        int k = nextInt();
        char[] arr = nextString().toCharArray();
        if (k == 2) {
            char[] res1 = new char[n];
            char[] res2 = new char[n];
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    res1[i] = 'B';
                    res2[i] = 'A';
                }
                else {
                    res1[i] = 'A';
                    res2[i] = 'B';
                }
            }

            int cnt1 = 0;
            int cnt2 = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] != res1[i]) {
                    cnt1++;
                }

                if (arr[i] != res2[i]) {
                    cnt2++;
                }
            }

            if (cnt1 < cnt2) {
                outln(cnt1);
                out(new String(res1));
            }
            else {
                outln(cnt2);
                out(new String(res2));
            }

            return;
        }

        int start = 0;
        int res = 0;
        while (start < n) {
            int end = start;
            while (end < n && arr[end] == arr[start]) {
                end++;
            }

            int cnt = end - start;
            if (cnt % 2 != 0) {
                char ch = nextChar(arr[start], arr[start]);
                for (int i = start + 1; i < end; i += 2) {
                    arr[i] = ch;
                    res++;
                }
            }
            else {
                char ch;
                if (end != n) {
                    ch = nextChar(arr[start], arr[end]);
                }
                else {
                    ch = nextChar(arr[start], arr[start]);
                }

                for (int i = start + 1; i < end; i += 2) {
                    arr[i] = ch;
                    res++;
                }
            }

            start = end;
        }

        outln(res);
        out(new String(arr));
    }

    char nextChar(char c1, char c2) {
        for (char c = 'A'; c <= 'Z'; c++) {
            if (c != c1 && c != c2) {
                return c;
            }
        }

        return 'a';
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    void swap(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}