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() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  if (k == 2) {
    string a = s, b = s;
    int ca = 0, cb = 0;
    for (int i = 0; i < a.size(); i++) {
      a[i] = (i % 2) ? 'B' : 'A';
      ca += a[i] != s[i];
    }
    for (int i = 0; i < b.size(); i++) {
      b[i] = (i % 2) ? 'A' : 'B';
      cb += b[i] != s[i];
    }
    if (ca < cb) {
      cout << ca << endl;
      cout << a << endl;
    } else {
      cout << cb << endl;
      cout << b << endl;
    }
  } else {
    vector<char> c(1, s[0]);
    vector<int> f(1, 0);
    for (char a : s) {
      if (a == c.back()) {
        f.back()++;
      } else {
        c.push_back(a);
        f.push_back(1);
      }
    }
    char pre, sub;
    int cost = 0, ind = 0;
    string fs = s;
    for (int i = 0; i < c.size(); i++) {
      cost += f[i] / 2;
      pre = (i ? c[i - 1] : 0);
      if (f[i] == 1) {
        ind++;
        continue;
      }
      if (f[i] % 2) {
        sub = 'B';
        if (c[i] == 'B') sub = 'A';
        for (int j = 0; j < f[i]; j++) {
          if (j % 2) {
            fs[ind] = sub;
          }
          ind++;
        }
      } else {
        sub = 'B';
        if (c[i] == 'B') sub = 'A';
        set<char> s;
        s.insert('A');
        s.insert('B');
        s.insert('C');
        s.erase(pre);
        s.erase(c[i]);
        sub = *s.begin();
        for (int j = 0; j < f[i]; j++) {
          if (j % 2 == 0) {
            fs[ind] = sub;
          }
          ind++;
        }
      }
    }
    cout << cost << endl;
    cout << fs << endl;
  }
  return 0;
}