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 main() {
  long long n, k;
  string s;
  cin >> n >> k >> s;
  if (k == 2) {
    string t1 = "", t2 = "";
    long long k1 = 0, k2 = 0;
    for (long long i = 0; i < n; i++) {
      if (i % 2) {
        t1 += "A";
        t2 += "B";
      } else {
        t1 += "B";
        t2 += "A";
      }
    }
    for (long long i = 0; i < n; i++) {
      if (s[i] == t1[i])
        k2++;
      else
        k1++;
    }
    if (k1 < k2) {
      cout << k1 << endl << t1;
    } else {
      cout << k2 << endl << t2;
    }
  } else {
    long long k = 0, ts = 0, te = 0;
    while (ts < n - 1) {
      te = ts;
      while (s[ts] == s[te] && te < n) te++;
      te--;
      if (te != ts) {
        if ((te - ts) % 2 == 0) {
          char c = 'A';
          k += (te - ts) / 2;
          if (s[ts] == 'A') c = 'B';
          for (long long i = ts + 1; i <= te - 1; i += 2) {
            s[i] = c;
          }
        } else {
          char c = 'A';
          if (s[ts] == 'A') c = 'B';
          if (te < n - 1 && s[te + 1] == c) c = 'C';
          if (c == 'C' && te < n - 1 && s[te + 1] == 'A' && s[ts] == 'C')
            c = 'B';
          k += (te - ts + 1) / 2;
          for (long long i = ts + 1; i <= te; i += 2) {
            s[i] = c;
          }
        }
      }
      ts = te + 1;
    }
    cout << k << endl << s;
  }
  return 0;
}