该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

贝西的键盘只有两个按键：M 和 O。
她想要打出她最喜欢的字符串 $S$（由 M 和 O 组成，长度为 $N$）。
但是她的电脑中了病毒：每次她按下 O 时，之前已经打出的所有字符都会翻转（M 变成 O，O 变成 M），然后再把 O 添加到字符串末尾。
按下 M 时则直接追加 M，不会发生翻转。

你需要判断贝西能否打出目标字符串 $S$，并且在某些情况下还需要给出按键序列。

输入格式

第一行包含两个整数 $T$（测试用例数量，$1 \leq T \leq 10^4$）和 $k$（$0 \leq k \leq 1$）。
接下来每个测试用例包含两行：

• 第一行：整数 $N$（$1 \leq N \leq 2 \cdot 10^5$）
• 第二行：字符串 $S$（仅包含 M 和 O）

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

输出格式

对于每个测试用例：

• 如果无法打出 $S$，输出一行 NO。
• 如果可以打出 $S$：
  • 第一行输出 YES
  • 如果 $k = 1$，第二行输出一个长度为 $N$ 的字符串（由 M 和 O 组成），表示贝西需要按的按键序列（任意合法解均可）。

2 0
3
MOO
5
OOMOO

YES
YES

2 1
3
MOO
5
OOMOO

YES
OMO
YES
MOOMO

样例解释

当贝西按 MOOMO 时：

1. 按 M：当前字符串为 M
2. 按 O：M 翻转为 O，然后添加 O，得到 OO
3. 按 O：OO 翻转为 MM，然后添加 O，得到 MMO
4. 按 M：直接添加 M，得到 MMOM
5. 按 O：MMOM 翻转为 OOMO，然后添加 O，得到 OOMOO，即目标字符串

数据规模与约定

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