D. Мириан и спички
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Спички Мириана представляют собой таблицу размером $$$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$$$) — количество столбцов спички и требуемое количество пар соседних клеток, имеющих различные буквы.

Вторая строка каждого набора содержит строку $$$s$$$ из $$$n$$$ символов ($$$s_i$$$ может быть либо A, либо B) — верхняя строка спички Мирианы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора, если нет способа заполнить вторую строку так, чтобы количество пар соседних клеток, имеющих различные буквы, было равно $$$k$$$, выведите «NO».

В противном случае выведите «YES». Затем выведите $$$n$$$ символов, которые представляют собой допустимую нижнюю строку для спички Мириана. Если есть несколько ответов, выведите любой из них.

Пример
Входные данные
4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB
Выходные данные
NO
YES
BABB
YES
ABABAABAB
NO
Примечание

В первом наборе можно доказать, что нет возможного способа заполнить $$$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$$$.