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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct node {
  int x;
  int y;
};
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
queue<int> Q;
stack<int> S;
int n, m;
int a, b, c;
int res;
int len, ans;
char s[500005], s2[500005], tmp;
char get(char a, char b) {
  int i;
  for (i = 0; i < m; ++i) {
    if (i != (a - 'A') && i != (b - 'A')) return i + 'A';
  }
}
int main() {
  int i, j, k;
  while (scanf("%d %d", &n, &m) != EOF) {
    scanf("%s", s + 1);
    s[0] = '$';
    len = strlen(s) - 1;
    ans = 0;
    if (m == 2) {
      strcpy(s2, s);
      for (i = 1; i <= len; ++i) {
        if (i % 2) {
          if (s[i] == 'B') {
            s[i] = 'A';
            ++ans;
          }
        } else {
          if (s[i] == 'A') {
            s[i] = 'B';
            ++ans;
          }
        }
      }
      int ans2 = 0;
      for (i = 1; i <= len; ++i) {
        if (i % 2 == 0) {
          if (s2[i] == 'B') {
            s2[i] = 'A';
            ++ans2;
          }
        } else {
          if (s2[i] == 'A') {
            s2[i] = 'B';
            ++ans2;
          }
        }
      }
      if (ans < ans2) {
        printf("%d\n", ans);
        printf("%s\n", s + 1);
      } else {
        printf("%d\n", ans2);
        printf("%s\n", s2 + 1);
      }
      continue;
    }
    for (i = 1; i <= len; ++i) {
      tmp = s[i];
      j = i;
      res = 1;
      while (s[j + 1] == tmp) {
        ++j;
        ++res;
      }
      if (res == 1) continue;
      if (res == 2) {
        ans += 1;
        s[i] = get(s[i - 1], s[i]);
      } else {
        ans += res / 2;
        char fuck = get(s[i], s[j + 1]);
        for (k = i + 1; k <= j; k += 2) {
          s[k] = fuck;
        }
      }
      i = j;
    }
    printf("%d\n", ans);
    printf("%s\n", s + 1);
  }
  return 0;
}