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 n, k;
string s;
const int N = 600000;
int dp[N][4], from[N][4];
int main() {
  cin >> n >> k >> s;
  if (k == 2) {
    int res = 0, ress = 0;
    for (int i = 0; i < n; i++) {
      res += s[i] != ('A' + i % 2);
      ress += s[i] != ('B' - i % 2);
    }
    cout << min(res, ress) << endl;
    for (int i = 0; i < n; i++)
      if (res < ress)
        cout << char('A' + i % 2);
      else
        cout << char('B' - i % 2);
    cout << endl;
    return 0;
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 4; j++) dp[i][j] = 1 << 29;
  if (s[0] <= 'C') {
    for (int i = 0; i < min(4, k); i++) dp[0][i] = 1;
    dp[0][s[0] - 'A'] = 0;
  } else
    dp[0][0] = dp[0][1] = dp[0][2] = 1, dp[0][3] = 0;
  for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++) {
        if ((k < 3 && j < 3 && k == j) ||
            (k == 3 && j == 3 && s[i] == s[i + 1]))
          continue;
        if (k == 3 && s[i + 1] < 'D') continue;
        int ch = k != 3 && s[i + 1] != ('A' + k);
        if (dp[i + 1][k] > dp[i][j] + ch) {
          dp[i + 1][k] = dp[i][j] + ch;
          from[i + 1][k] = j;
        }
      }
  int m = 0;
  for (int i = 0; i < 4; i++)
    if (dp[n - 1][i] < dp[n - 1][m]) m = i;
  cout << dp[n - 1][m] << endl;
  string ans;
  for (int i = n - 1; i >= 0; i--) {
    if (m < 3)
      ans += 'A' + m;
    else
      ans += s[i] > 'C' ? s[i] : 'D';
    m = from[i][m];
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}