题目描述

Bessie 有一个键盘，上面只有两个字母：M 和 O。

Bessie 想打出她最喜欢的哞哞字符串 $S$，该字符串由 $N$ 个字母组成，每个字母是 M 或 O。然而，她的电脑中了病毒。每次她尝试打出字母 O 时，她之前打出的所有字母都会翻转，从 M 变成 O 或从 O 变成 M，然后 O 才出现。

Bessie 有可能打出她最喜欢的哞哞字符串吗？

此外，Bessie 被给定一个参数 $k$，其值为 $0$ 或 $1$。

• 如果 $k = 0$，那么 Bessie 只需要判断是否可能打出她最喜欢的哞哞字符串。
• 如果 $k = 1$，那么 Bessie 还需要给出一个按键序列的例子，以便她能够打出她最喜欢的哞哞字符串。

输入格式

第一行包含 $T$，表示独立测试用例的数量（$1\le T\le 10^4$），和 $k$（$0 \le k \le 1$）。

每个测试用例的第一行有 $N$（$1 \le N \le 2 \cdot 10^5$）。

每个测试用例的第二行有 $S$。保证 $S$ 中除了 M 和 O 外不会出现其他字符。

所有测试用例的 $N$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，按照以下步骤输出一行或两行。

如果 Bessie 不可能打出 $S$，则在一行中打印 NO。

否则，在第一行打印 YES。此外，如果 $k=1$，在第二行打印一个长度为 $N$ 的字符串，表示 Bessie 需要按顺序打出的字母序列，以便打出她最喜欢的哞哞字符串。如果有多个这样的字符串，任意一个都可以接受。

输入输出样例 #1

输入 #1

2 0
3
MOO
5
OOMOO

输出 #1

YES
YES

输入输出样例 #2

输入 #2

2 1
3
MOO
5
OOMOO

输出 #2

YES
OMO
YES
MOOMO

说明/提示

当 Bessie 打出 MOOMO 时，字母的变化如下：

• 在打出第一个 M 之前，Bessie 有一个空字符串。之后，她有了字符串 M。
• 在打出第一个 O 之后，M 翻转为 O，然后 O 被追加，形成 OO。
• 在打出第二个 O 之后，OO 翻转为 MM，然后 O 被追加，形成 MMO。
• 在打出第二个 M 之后，Bessie 有了字符串 MMOM。
• 在打出最后一个 O 之后，字符串 MMOM 翻转为 OOMO，然后 O 被追加，形成 OOMOO，正如所愿。

评分

• 输入 3-4：$k=0$。
• 输入 5-6：$k=1, T \le 10^3, N \le 10$。
• 输入 7-9：$k=1, T \le 10, N \le 1000$。
• 输入 10-16：$k=1$。

翻译由 DeepSeek 完成