CF1852D.Miriany and Matchstick

Miriany's matchstick is a $2 \times n$ grid that needs to be filled with characters A or B.

He has already filled in the first row of the grid and would like you to fill in the second row. You must do so in a way such that the number of adjacent pairs of cells with different characters$^\dagger$ is equal to $k$. If it is impossible, report so.

$^\dagger$ An adjacent pair of cells with different characters is a pair of cells $(r_1, c_1)$ and $(r_2, c_2)$ ($1 \le r_1, r_2 \le 2$, $1 \le c_1, c_2 \le n$) such that $|r_1 - r_2| + |c_1 - c_2| = 1$ and the characters in $(r_1, c_1)$ and $(r_2, c_2)$ are different.

米里安妮的火柴棒是一个 $2 \times n$ 的网格，需要用字符 A 或 B 填满。

她已经填好了网格的第一行，现在请你填写第二行。你的填写方式必须使得字符不同的相邻格子对的数量恰好等于 $k$；若无法做到，请报告不可能。

$^\dagger$ 字符不同的相邻格子对是指一对格子 $(r_1, c_1)$ 和 $(r_2, c_2)$（其中 $1 \le r_1, r_2 \le 2$，$1 \le c_1, c_2 \le n$），满足 $|r_1 - r_2| + |c_1 - c_2| = 1$，且格子 $(r_1, c_1)$ 与 $(r_2, c_2)$ 中的字符不同。

The first line consists of an integer $t$, the number of test cases ($1 \leq t \leq 1000$). The description of the test cases follows.

The first line of each test case has two integers, $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 3 \cdot n$) – the number of columns of the matchstick, and the number of adjacent pairs of cells with different characters required.

The following line contains string $s$ of $n$ characters ($s_i$ is either A or B) – Miriany's top row of the matchstick.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$，表示测试用例的数量（$1 \leq t \leq 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq k \leq 3 \cdot n$）——分别表示火柴棒的列数，以及要求的相邻单元格中字符不同的对数。

下一行包含一个长度为 $n$ 的字符串 $s$（每个字符 $s_i$ 为 A 或 B）——即 Miriany 的火柴棒顶行。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, if there is no way to fill the second row with the number of adjacent pairs of cells with different characters equals $k$, output "NO".

Otherwise, output "YES". Then, print $n$ characters that a valid bottom row for Miriany's matchstick consists of. If there are several answers, output any of them.

对于每个测试用例，若无法在第二行填入字符，使得相邻且字符不同的单元格对的数量恰好等于 $k$，则输出 "NO"。

否则，输出 "YES"；然后输出 $n$ 个字符，表示 Miriany 的火柴棒图案中一个合法的底行。若存在多个合法答案，输出任意一个即可。

In the first test case, it can be proved that there exists no possible way to fill in row $2$ of the grid such that $k = 1$.

For the second test case, BABB is one possible answer.

The grid below is the result of filling in BABB as the second row.

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{array}$

The pairs of different characters are shown below in red:

$\begin{array}{|c|c|} \hline \color{red}{A} & A & A & A \cr \hline \color{red}{B} & A & B & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & \color{red}{A} & A \cr \hline B & A & \color{red}{B} & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & \color{red}{A} \cr \hline B & A & B & \color{red}{B} \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline \color{red}{B} & \color{red}{A} & B & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & \color{red}{A} & \color{red}{B} & B \cr \hline \end{array}$

There are a total of $5$ pairs, which satisfies $k$.

在第一个测试用例中，可以证明：不存在任何方式来填写网格的第 $2$ 行，使得 $k = 1$。

在第二个测试用例中，BABB 是一个可能的答案。

下图是将 BABB 填入第二行后得到的网格：

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{array}$

以下用红色标出了所有字符不同的配对：

$\begin{array}{|c|c|} \hline \color{red}{A} & A & A & A \cr \hline \color{red}{B} & A & B & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & \color{red}{A} & A \cr \hline B & A & \color{red}{B} & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & \color{red}{A} \cr \hline B & A & B & \color{red}{B} \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline \color{red}{B} & \color{red}{A} & B & B \cr \hline \end{array}$

—————————————————

$\begin{array}{|c|c|} \hline A & A & A & A \cr \hline B & \color{red}{A} & \color{red}{B} & B \cr \hline \end{array}$

共有 $5$ 对，满足 $k$ 的要求。