首先考虑到第一行是固定的，先去掉第一行的贡献。
接下来会有一个 \(O(n^2)\) 的 \(\text{DP}\)。
考虑设 \(f_{i, 0 / 1, j}\) 为考虑了 \(1\sim i\) 列的放置，第 \(i\) 列填 \(\text{A / B}\) 且对数为 \(j\) 是否可行。
分讨第 \(i\) 列的取值与 \(i - 1\) 列的即可转移：
第 \(i\) 列与第 \(i - 1\) 列若不同则 \(+1\)，若与第 \(i\) 列第一行不同 \(+1\)。
考虑优化，发现最多也只能用个 bitset 达到 \(O(\frac{n^2}{w})\) 的复杂度，还是不理想。
打个表能发现对于 \(f_{i, p}\)，存在 \(l, r\) 满足对于 \(\sum\limits_{j \in [l, r]} [f_{i, p, j} = 0] \le 1, \sum\limits_{j \in ([0, 3n]/ [i, j])} [f_{i, p, j} = 1] = 0\)。
于是可以考虑 \(f_{i, p}\) 维护 \([l, r]\)，如果中间有一个断点考虑维护下这个断点即可。
转移的时候依然分讨然后合并即可。
时间复杂度 \(O(n)\)。
证明如下（参考了这篇题解）。
考虑到转移只有可能 \(0, +1, +2\)，且 \(+1\) 是无论选 \(\text{A / B}\) 都是有的，只需考虑第 \(i - 1\) 位填的与第 \(i\) 列第一行不同的情况，那不妨考虑成 \(-1, 0, +1\)。
那么说明两个状态的 \(l, r\) 相差均不超过 \(2\)，因为是 \(-1\) 和 \(+1\) 的区别。
考虑第 \(f_{i - 1}\) 存在至少一个状态 \(r - l + 1\ge 5\) 的时候，最坏情况下相对的状态 \(l' = l + 2, r' = r - 2\)。
若两个状态都没有断点或 \([l', r']\) 有断点，则 \(f_i\) 的两个状态必然是没有断点的。
若 \([l, r]\) 存在断点 \(x\)，则肯定有 \(l < x < r\) 即 \(l + 1\le x\le r - 1\)，那至多会有一个断点，\([l', r']\) 若有断点则肯定会被 \([l, r]\) 覆盖。
接下来考虑 \(r - l + 1 < 5\) 的，这部分打表即可，因为规模很小也可以手模：
\(\begin{matrix}
\begin{bmatrix}00010000\\00001000\end{bmatrix}
&\to &\begin{bmatrix}00010000\\00010100\end{bmatrix}
&\to &\begin{bmatrix}00110100\\00011100\end{bmatrix}
&\to &\begin{bmatrix}01111100\\00011110\end{bmatrix} \\
\cdots
&\to &\cdots
&\to &\cdots
&\to &\begin{bmatrix}00111100\\00111110\end{bmatrix} \\
\cdots
&\to &\cdots
&\to &\begin{bmatrix}00111000\\00011010\end{bmatrix}
&\to &\begin{bmatrix}01111010\\00011110\end{bmatrix} \\
\cdots
&\to &\cdots
&\to &\cdots
&\to &\begin{bmatrix}00111100\\00111101\end{bmatrix} \\
\cdots
&\to &\begin{bmatrix}00101000\\00001000\end{bmatrix}
&\to &\cdots
&\to &\cdots
\end{matrix}\)
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
struct F {
int p, l, r;
inline bool h(const int &x) const {return l <= x && x <= r && x != p;}
inline F w(const int &d) const {return F{p == -1 ? -1 : (p + d), l + d, r + d};}
inline F operator * (const F &o) const {
int L = std::min(l, o.l), R = std::max(r, o.r);
if (r + 2 == o.l) return {r + 1, L, R};
if (o.r + 2 == l) return {l - 1, L, R};
if (p != -1 && ! o.h(p)) return {p, L, R};
if (o.p != -1 && ! h(o.p)) return {o.p, L, R};
return {-1, L, R};
}
} f[maxn][2];
char s_[maxn]; int s[maxn];
inline void solve() {
int n, k; scanf("%d%d%s", &n, &k, s_ + 1);
for (int i = 1; i <= n; i++) s[i] = s_[i] - 'A';
for (int i = 1; i < n; i++) k -= s[i] != s[i + 1];
if (k < 0) return puts("NO"), void();
f[1][s[1]] = F{-1, 0, 0}, f[1][1 - s[1]] = F{-1, 1, 1};
for (int i = 2; i <= n; i++) {
f[i][s[i]] = f[i - 1][s[i]] * (f[i - 1][1 - s[i]].w(1));
f[i][1 - s[i]] = (f[i - 1][1 - s[i]] * (f[i - 1][s[i]].w(1))).w(1);
}
int tp = f[n][0].h(k) ? 0 : (f[n][1].h(k) ? 1 : -1);
if (tp == -1) return puts("NO"), void();
for (int i = n; i; i--) {
s_[i] = 'A' + tp;
! f[i - 1][tp].h(k -= (tp != s[i])) && (k--, tp ^= 1);
}
printf("YES\n%s\n", s_ + 1);
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}