Miriany 的火柴棍是一个 $$$2 \times n$$$ 网格,需要填充字符 A 或 B。
他已经填写了网格的第一行,并希望您填写第二行。这样做的方式必须使具有不同字符$$$^\dagger$$$ 的相邻单元对的数量等于 $$$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)$$$ 中的字符不同。
输入
第一行由一个整数 $$$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$$$。
输出
对于每个测试用例,如果无法用具有不同字符的相邻单元格对的数量等于 $$$k$$$ 填充第二行,则输出“NO”。
否则,输出“YES”。然后,打印 Miriany 火柴棍的有效底行所包含的 $$$n$$$ 个字符。如果有多个答案,则输出其中一个。
示例
输入 #1
4 10 1 ABBAAABBAA 4 5 AAAA 9 17 BAAABBAAB 4 9 ABAB
输出 #1
NO YES BABB YES ABABAABAB NO
注意
在第一个测试用例中,可以证明不存在可能的方法来填充网格的行 $$$2$$$ 使得 $$$k = 1$$$。
对于第二个测试用例,BABB 是一个可能的答案。
下面的网格是第二行填写BABB的结果。
$$$\begin{数组}{|c|c|} \hline A & A & A & A \cr \hline B & A & B & B \cr \hline \end{数组}$$$
不同字符对如下以红色显示:
$$$\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$$$。