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 OO = (int)2e9;
const double eps = 1e-9;
char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
                  'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                  's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
char ALPHA[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                  'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
                  'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
int daysInMonths[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
int main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k, res = 0;
  string s;
  cin >> n >> k >> s;
  if (k == 2) {
    string tmp1, tmp2;
    char a = 'A', b = 'B';
    while (true) {
      tmp1 += a;
      if (tmp1.size() == s.size()) break;
      tmp1 += b;
      if (tmp1.size() == s.size()) break;
    }
    while (true) {
      tmp2 += b;
      if (tmp2.size() == s.size()) break;
      tmp2 += a;
      if (tmp2.size() == s.size()) break;
    }
    int diff1 = 0, diff2 = 0;
    for (int i = 0; i < (int)s.size(); i++) {
      if (tmp1[i] != s[i]) diff1++;
      if (tmp2[i] != s[i]) diff2++;
    }
    if (diff1 < diff2)
      cout << diff1 << endl << tmp1;
    else
      cout << diff2 << endl << tmp2;
  } else {
    for (int i = 0; i < (int)s.size(); i++) {
      if (s[i] == s[i + 1]) {
        res++;
        for (int j = 0; j < k; j++) {
          if (ALPHA[j] != s[i] && ALPHA[j] != s[i + 2]) {
            s[i + 1] = ALPHA[j];
            break;
          }
        }
      }
    }
    cout << res << endl << s;
  }
  return 0;
}