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 nn = '\n';
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
long long power(long long n, long long p) {
  long long res = 1;
  while (p) {
    if (p % 2) {
      res *= n;
      p--;
    } else {
      n *= n;
      p /= 2;
    }
  }
  return res;
}
void solve() {
  long long n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  long long count = 0;
  if (k == 2) {
    string temp1(n, 'A');
    string temp2(n, 'B');
    for (int i = 1; i < n; i += 2) temp1[i] = 'B', temp2[i] = 'A';
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++)
      if (temp1[i] != s[i])
        cnt1++;
      else
        cnt2++;
    if (cnt1 < cnt2)
      cout << cnt1 << "\n" << temp1;
    else
      cout << cnt2 << "\n" << temp2;
    return;
  }
  s = '#' + s + '#';
  for (long long i = 1; i < n + 1; i++) {
    if (s[i] == s[i - 1]) {
      for (int x = 0; x < k; x++) {
        char r = 'A' + x;
        if (r == s[i - 1] || r == s[i + 1]) continue;
        s[i] = r;
        count++;
        break;
      }
    }
  }
  cout << count << nn;
  cout << s.substr(1, n);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}