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;
const int MAXN = 5e5 + 10;
int n, k;
int dp[MAXN];
int mark[MAXN];
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  string s;
  cin >> n >> k >> s;
  dp[0] = 1;
  mark[0] = 1;
  int ans = 0;
  for (int ii = 1; ii < n; ii++) {
    if (s[ii] == s[ii - 1])
      dp[ii] = dp[ii - 1] + 1;
    else
      dp[ii] = 1, mark[ii] = 1;
  }
  if (k == 2) {
    int c1 = 0, c2 = 1, cnt1 = 0, cnt2 = 0;
    for (int ii = 0; ii < s.size(); ii++) {
      if (c1 != s[ii] - 'A') cnt1++;
      c1 ^= 1;
      if (c2 != s[ii] - 'A') cnt2++;
      c2 ^= 1;
    }
    if (cnt1 < cnt2) {
      cout << cnt1 << endl;
      c1 = 0;
      for (int ii = 0; ii < n; ii++) {
        cout << char('A' + c1);
        c1 ^= 1;
      }
    } else {
      cout << cnt2 << endl;
      c2 = 1;
      for (int ii = 0; ii < n; ii++) {
        cout << char('A' + c2);
        c2 ^= 1;
      }
    }
    return 0;
  }
  s += s.back();
  mark[n] = 1;
  for (int ii = 1; ii <= n; ii++) {
    if (mark[ii]) {
      ans += dp[ii - 1] / 2;
      int color = -1;
      int c1 = s[ii - 1] - 'A', c2 = s[ii] - 'A';
      if (dp[ii - 1] % 2 == 1 && ii != n) color = s[ii] - 'A';
      for (int kk = 0; kk < k; kk++) {
        if (kk != c1 && kk != c2) {
          color = kk;
          break;
        }
      }
      int doit = 0;
      for (int kk = ii - dp[ii - 1]; kk < ii; kk++) {
        if (doit) s[kk] = 'A' + color;
        doit = doit ^ 1;
      }
    }
  }
  cout << ans << endl;
  for (int ii = 0; ii < n; ii++) {
    cout << s[ii];
  }
}