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 B[500000][2];
int C[26];
int main() {
  int n, k;
  string str;
  cin >> n >> k >> str;
  int id0 = str.at(0) - 'A', id1 = 0, val0 = 0, val1 = 1;
  for (int j = 0; j < k; ++j) {
    if (id0 != j) {
      id1 = j;
      break;
    }
  }
  B[0][0] = id0;
  B[0][1] = id1;
  for (int i = 1; i < n; ++i) {
    int id = str.at(i) - 'A';
    for (int j = 0; j < k; ++j) {
      if (j != id0) {
        if (id == j)
          C[j] = val0;
        else
          C[j] = val0 + 1;
      } else {
        if (id == j)
          C[j] = val1;
        else
          C[j] = val1 + 1;
      }
    }
    int v0, v1;
    if (C[0] < C[1]) {
      id0 = 0;
      v0 = C[0];
      id1 = 1;
      v1 = C[1];
    } else {
      id0 = 1;
      v0 = C[1];
      id1 = 0;
      v1 = C[0];
    }
    for (int j = 2; j < k; ++j) {
      if (C[j] < v0) {
        v1 = v0;
        v0 = C[j];
        id1 = id0;
        id0 = j;
      } else if (C[j] < val1) {
        v1 = C[j];
        id1 = j;
      }
    }
    val0 = v0;
    val1 = v1;
    B[i][0] = id0;
    B[i][1] = id1;
  }
  string result(n, 'A');
  if (val0 < val1) {
    cout << val0 << endl;
    result.at(n - 1) = B[n - 1][0] + 'A';
  } else {
    cout << val1 << endl;
    result.at(n - 1) = B[n - 1][1] + 'A';
  }
  for (int i = n - 2; i >= 0; --i) {
    if (result.at(i + 1) - 'A' == B[i][0])
      result.at(i) = B[i][1] + 'A';
    else
      result.at(i) = B[i][0] + 'A';
  }
  cout << result;
  return 0;
}