310573: CF1853F. Miriany and Matchstick
Description
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.
InputThe 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$.
OutputFor 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.
ExampleInput4 10 1 ABBAAABBAA 4 5 AAAA 9 17 BAAABBAAB 4 9 ABABOutput
NO YES BABB YES ABABAABAB NONote
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.
The pairs of different characters are shown below in red:
—————————————————
$\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$.
Input
Output
米里亚尼的火柴棍是一个 $2 \times n$ 的网格，需要用字符 'A' 或 'B' 填充。他已经填写了网格的第一行，请你填写第二行，使得不同字符的相邻单元格对数等于 $k$。如果不可能，则报告不可能。
输入数据格式：
第一行包含一个整数 $t$，表示测试用例的数量 ($1 \leq t \leq 1000$)。
每个测试用例包含以下内容：
- 第一行有两个整数 $n$ 和 $k$ ($1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 3 \times n$)，分别表示网格的列数和不同字符的相邻单元格对数。
- 下一行包含一个长度为 $n$ 的字符串 $s$（$s_i$ 要么是 'A'，要么是 'B'），表示米里亚尼的火柴棍的第一行。
输出数据格式：
对于每个测试用例，如果无法填充第二行使得不同字符的相邻单元格对数等于 $k$，则输出 "NO"。
否则，输出 "YES"，然后打印一个有效的第二行字符串。如果有多个答案，输出其中任何一个。
示例：
```
Input
4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB
Output
NO
YES
BABB
YES
ABABAABAB
NO
```
注意：
在第二个测试用例中，"BABB" 是一个可能的答案。如下所示，红色标出了不同字符的相邻单元格对：
```
A A A A
B A B B
```
红色对的总数是 5，满足 $k$。题目大意： 米里亚尼的火柴棍是一个 $2 \times n$ 的网格，需要用字符 'A' 或 'B' 填充。他已经填写了网格的第一行，请你填写第二行，使得不同字符的相邻单元格对数等于 $k$。如果不可能，则报告不可能。 输入数据格式： 第一行包含一个整数 $t$，表示测试用例的数量 ($1 \leq t \leq 1000$)。 每个测试用例包含以下内容： - 第一行有两个整数 $n$ 和 $k$ ($1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 3 \times n$)，分别表示网格的列数和不同字符的相邻单元格对数。 - 下一行包含一个长度为 $n$ 的字符串 $s$（$s_i$ 要么是 'A'，要么是 'B'），表示米里亚尼的火柴棍的第一行。 输出数据格式： 对于每个测试用例，如果无法填充第二行使得不同字符的相邻单元格对数等于 $k$，则输出 "NO"。 否则，输出 "YES"，然后打印一个有效的第二行字符串。如果有多个答案，输出其中任何一个。 示例： ``` Input 4 10 1 ABBAAABBAA 4 5 AAAA 9 17 BAAABBAAB 4 9 ABAB Output NO YES BABB YES ABABAABAB NO ``` 注意： 在第二个测试用例中，"BABB" 是一个可能的答案。如下所示，红色标出了不同字符的相邻单元格对： ``` A A A A B A B B ``` 红色对的总数是 5，满足 $k$。