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 dp[500005][28];
int ar[500005];
int p[500005][28];
int ans[500005];
string st;
int main() {
  int a, b, c, d, e, x, y, z, k, n;
  cin >> n >> k;
  cin >> st;
  for (a = 0; a < n; a++) ar[a + 1] = st[a] - 'A';
  for (a = 1; a <= n; a++) {
    for (b = 0; b < k; b++) {
      dp[a][b] = 500005;
    }
  }
  for (a = 1; a <= n; a++) {
    for (b = 0; b < k; b++) {
      if (ar[a] == b)
        c = 0;
      else
        c = 1;
      for (d = 0; d < k; d++) {
        if (b == d) continue;
        if (dp[a][b] > dp[a - 1][d] + c) {
          dp[a][b] = min(dp[a][b], dp[a - 1][d] + c);
          p[a][b] = d;
        }
      }
    }
  }
  x = 500005;
  for (a = 0; a < k; a++)
    if (x > dp[n][a]) {
      x = dp[n][a];
      b = a;
    }
  cout << x << endl;
  a = n;
  while (a >= 1) {
    ans[a] = b;
    b = p[a][b];
    a--;
  }
  for (a = 1; a <= n; a++) printf("%c", ans[a] + 'A');
  printf("\n");
  return 0;
}