Спички Мириана представляют собой таблицу размером \(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)\) различаются.
Выходные данные
Для каждого набора, если нет способа заполнить вторую строку так, чтобы количество пар соседних клеток, имеющих различные буквы, было равно \(k\), выведите «NO».
В противном случае выведите «YES». Затем выведите \(n\) символов, которые представляют собой допустимую нижнюю строку для спички Мириана. Если есть несколько ответов, выведите любой из них.
Примечание
В первом наборе можно доказать, что нет возможного способа заполнить \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 1
ABBAAABBAA
4 5
AAAA
9 17
BAAABBAAB
4 9
ABAB
|
NO
YES
BABB
YES
ABABAABAB
NO
|