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;
char str[1001000];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    cin >> str[i];
  }
  if (k == 2) {
    int sum = 0, sum1 = 0;
    char tmp = 'A';
    for (int i = 1; i <= n; i++) {
      if (str[i] != tmp) {
        tmp = str[i];
      } else {
        if (tmp == 'A')
          tmp = 'B';
        else
          tmp = 'A';
        sum++;
      }
    }
    tmp = 'B';
    for (int i = 1; i <= n; i++) {
      if (str[i] != tmp) {
        tmp = str[i];
      } else {
        if (tmp == 'A')
          tmp = 'B';
        else
          tmp = 'A';
        sum1++;
      }
    }
    if (sum < sum1) {
      printf("%d\n", sum);
      for (int i = 1; i <= n; i++) {
        if (i % 2 == 0)
          printf("A");
        else
          printf("B");
      }
    } else {
      printf("%d\n", sum1);
      for (int i = 1; i <= n; i++) {
        if (i % 2 == 0)
          printf("B");
        else
          printf("A");
      }
    }
  } else {
    int sum = 0, cnt = 1;
    char tmp = '#';
    char tc;
    for (int j = 0; j < k; j++) {
      if ((j + 'A') != str[n]) {
        tc = j + 'A';
        break;
      }
    }
    str[n + 1] = tc;
    for (int i = 1; i <= n + 1; i++) {
      if (str[i] != tmp) {
        if (cnt == 1) {
          tmp = str[i];
          continue;
        }
        char tc;
        for (int j = 0; j < k; j++) {
          if ((j + 'A') != tmp && (j + 'A') != str[i]) {
            tc = j + 'A';
          }
        }
        if (cnt % 2 == 0) {
          str[i - 1] = tc;
          for (int j = i - 3; (i - j) <= cnt; j -= 2) str[j] = tc;
          sum += 1 + (cnt - 1) / 2;
        } else {
          for (int j = i - 2; (i - j) <= cnt; j -= 2) str[j] = tc;
          sum += cnt / 2;
        }
        cnt = 1;
        tmp = str[i];
      } else {
        cnt++;
      }
    }
    printf("%d\n", sum);
    for (int i = 1; i <= n; i++) printf("%c", str[i]);
  }
  return 0;
}