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;
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  char line[n + 1];
  scanf("%s", line);
  if (k == 2) {
    char tmp1[n], tmp2[n];
    for (int i = 0; i < n; i++) {
      tmp1[i] = (i % 2 == 0 ? 'A' : 'B');
      tmp2[i] = (i % 2 == 0 ? 'B' : 'A');
    }
    tmp1[n] = '\0';
    tmp2[n] = '\0';
    int dis1 = 0;
    int dis2 = 0;
    for (int i = 0; i < n; i++) {
      if (tmp1[i] != line[i]) dis1++;
      if (tmp2[i] != line[i]) dis2++;
    }
    if (dis1 >= dis2)
      printf("%d\n%s", dis2, tmp2);
    else
      printf("%d\n%s", dis1, tmp1);
  } else {
    int total = 0;
    for (int i = 0; i < n;) {
      int len = 1;
      for (int j = i + 1; j < n; j++) {
        if (line[i] == line[j])
          len++;
        else
          break;
      }
      total += len / 2;
      if (len > 1) {
        char c;
        for (int k = 0; k < 25; k++) {
          if ('A' + k != line[i] && 'A' + k != line[i + len]) {
            c = 'A' + k;
            break;
          }
        }
        for (int k = 0; k < len; k++) {
          if (k % 2 == 1) line[i + k] = c;
        }
      }
      i += len;
    }
    printf("%d\n%s", total, line);
  }
  return 0;
}