310565: CF1852D. Miriany and Matchstick

D. Miriany and Matchsticktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB

Output

NO
YES
BABB
YES
ABABAABAB
NO

Note

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$.

**题目大意**：

Miriany有一个2×n的火柴棍格子，需要用字符A或B填充。他已经填写了格子的第一行，现在需要你填写第二行，要求填写的方式是使得不同字符的相邻单元格对的数量等于k。如果不可能，则报告不可能。

**输入数据格式**：

第一行包含一个整数t，表示测试用例的数量（1≤t≤1000）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5，0≤k≤3×n），分别表示火柴棍格子的列数和不同字符的相邻单元格对的数量要求。

接下来的一行包含一个由n个字符组成的字符串s（si是A或B），表示Miriany的火柴棍格子的顶行。

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

**输出数据格式**：

对于每个测试用例，如果不存在一种方式使得不同字符的相邻单元格对的数量等于k，则输出"NO"。

否则，输出"YES"，然后打印出一个有效的Miriany火柴棍格子底行由n个字符组成的字符串。如果有多个答案，输出其中任何一个。

**示例**：

输入：
```
4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB
```
输出：
```
NO
YES
BABB
YES
ABABAABAB
NO
```

**注意**：

- 在第一个测试用例中，可以证明不存在一种方式填写第二行使得k=1。
- 对于第二个测试用例，BABB是可能的答案之一。
- 对于第二个测试用例，填写BABB后，有5对不同字符的相邻单元格对，满足k的要求。**题目大意**： Miriany有一个2×n的火柴棍格子，需要用字符A或B填充。他已经填写了格子的第一行，现在需要你填写第二行，要求填写的方式是使得不同字符的相邻单元格对的数量等于k。如果不可能，则报告不可能。 **输入数据格式**： 第一行包含一个整数t，表示测试用例的数量（1≤t≤1000）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数n和k（1≤n≤2×10^5，0≤k≤3×n），分别表示火柴棍格子的列数和不同字符的相邻单元格对的数量要求。 接下来的一行包含一个由n个字符组成的字符串s（si是A或B），表示Miriany的火柴棍格子的顶行。 保证所有测试用例的n之和不超过2×10^5。 **输出数据格式**： 对于每个测试用例，如果不存在一种方式使得不同字符的相邻单元格对的数量等于k，则输出"NO"。 否则，输出"YES"，然后打印出一个有效的Miriany火柴棍格子底行由n个字符组成的字符串。如果有多个答案，输出其中任何一个。 **示例**： 输入： ``` 4 10 1 ABBAAABBAA 4 5 AAAA 9 17 BAAABBAAB 4 9 ABAB ``` 输出： ``` NO YES BABB YES ABABAABAB NO ``` **注意**： - 在第一个测试用例中，可以证明不存在一种方式填写第二行使得k=1。 - 对于第二个测试用例，BABB是可能的答案之一。 - 对于第二个测试用例，填写BABB后，有5对不同字符的相邻单元格对，满足k的要求。