P15254 [USACO26JAN2] It's Mooin' Time IV B

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 需要按顺序打出的字母序列，以便打出她最喜欢的哞哞字符串。如果有多个这样的字符串，任意一个都可以接受。

当 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 完成