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;
pair<long long int, long long int> getans(string s) {
  long long int a1 = 0, a2 = 0;
  long long int n = s.length();
  long long int c1 = 0, c2 = 1;
  for (long long int i = 0; i < n; i++) {
    long long int x = s[i] - 'A';
    a1 += abs(c1 - x);
    c1 = (c1 + 1) % 2;
    a2 += abs(c2 - x);
    c2 = (c2 + 1) % 2;
  }
  if (a1 <= a2)
    return {a1, 0};
  else
    return {a2, 1};
}
char notthese(char c1, char c2) {
  for (char i = 'A'; i <= 'Z'; i++) {
    if (i != c1 && i != c2) return i;
  }
  return 'X';
}
void solve(long long int T) {
  long long int n, k;
  cin >> n >> k;
  string s, p;
  cin >> s;
  p = s;
  if (s.length() == 1) {
    cout << 0 << endl;
    cout << s << endl;
    return;
  }
  if (k == 2) {
    pair<long long int, long long int> p = getans(s);
    cout << p.first << endl;
    long long int x = p.second;
    long long int ch = 'A';
    for (long long int i = 0; i < n; i++) {
      cout << char(ch + x);
      x = (x + 1) % 2;
    }
    return;
  }
  for (long long int i = 1; i < n - 1; i++) {
    if (s[i] == s[i - 1] && s[i] == s[i + 1]) {
      if (s[i] == 'A')
        s[i] = 'B';
      else
        s[i] = 'A';
    }
  }
  for (long long int i = 1; i < n; i++) {
    if (s[i] == s[i - 1]) {
      if (i + 1 < n)
        s[i] = notthese(s[i], s[i + 1]);
      else {
        if (s[i] == 'A')
          s[i] = 'B';
        else
          s[i] = 'A';
      }
    }
  }
  long long int ans = 0;
  for (long long int i = 0; i < n; i++) {
    if (s[i] != p[i]) {
      ans++;
    }
  }
  cout << ans << endl;
  cout << s << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int T = 1;
  for (long long int t = 1; t <= T; t++) {
    solve(t);
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}