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 dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, k;
string s;
int DP[5 * 100001][27];
int solve(int i, char last) {
  if (i == n) return 0;
  int& ret = DP[i][last - 'A'];
  if (ret != -1) return ret;
  ret = 1e9;
  if (s[i] != last) ret = min(ret, solve(i + 1, s[i]));
  for (char j = 'A'; j <= min(char('A' + k - 1), 'C'); j++)
    if (j != last) ret = min(ret, solve(i + 1, j) + (s[i] != j));
  return ret;
}
void print(int i, char last) {
  if (i == n) {
    printf("\n");
    return;
  }
  if (s[i] != last) {
    if (DP[i][last - 'A'] == solve(i + 1, s[i])) {
      printf("%c", s[i]);
      print(i + 1, s[i]);
      return;
    }
  }
  for (char j = 'A'; j <= min(char('A' + k - 1), 'C'); j++) {
    if (j != last) {
      if (DP[i][last - 'A'] == solve(i + 1, j) + (s[i] != j)) {
        printf("%c", j);
        print(i + 1, j);
        return;
      }
    }
  }
}
int main() {
  scanf("%d %d", &n, &k);
  cin >> s;
  memset(DP, -1, sizeof(DP));
  printf("%d\n", solve(0, '['));
  print(0, '[');
  return 0;
}