Bessie 有一台键盘上只有 M 和 O 两个字母的电脑。

Bessie 想要输入她最喜欢的 moo 字符串 $S$，该字符串由 $N$ 个字母组成，每个字母要么是 M，要么是 O。然而，她的电脑感染了病毒。每当她尝试输入字母 O 时，她目前为止输入的所有字母都会翻转（M 变为 O，或 O 变为 M），然后 O 才会出现。

Bessie 是否有可能输入她最喜欢的 moo 字符串？

此外，Bessie 会得到一个参数 $k$，其值为 $0$ 或 $1$。

• 如果 $k = 0$，Bessie 只需要判断是否有可能输入她最喜欢的 moo 字符串。
• 如果 $k = 1$，Bessie 还需要给出一个按键序列示例，以便她能输入她最喜欢的 moo 字符串。

输入格式

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

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

每个测试用例的第二行包含 $S$。保证 $S$ 中只会出现 $\texttt{M}$ 和 $\texttt{O}$。

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

输出格式

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

如果 Bessie 不可能输入 $S$，则在单独的一行中输出 $\texttt{NO}$。

否则，第一行输出 $\texttt{YES}$。此外，如果 $k=1$，则在第二行输出一个长度为 $N$ 的字符串，表示 Bessie 为了输入她最喜欢的 moo 字符串所需要按下的字符序列。如果存在多个这样的字符串，输出其中任意一个即可。

样例

输入 1

2 0
3
MOO
5
OOMOO

输出 1

YES
YES

输入 2

2 1
3
MOO
5
OOMOO

输出 2

YES
OMO
YES
MOOMO

说明

当 Bessie 输入 $\texttt{MOOMO}$ 时，字母的变化过程如下：

1. 在输入第一个 $\texttt{M}$ 之前，Bessie 有一个空字符串。输入后，她得到字符串 $\texttt{M}$。
2. 在输入第一个 $\texttt{O}$ 后，$\texttt{M}$ 翻转为 $\texttt{O}$，然后追加 $\texttt{O}$ 形成 $\texttt{OO}$。
3. 在输入第二个 $\texttt{O}$ 后，$\texttt{OO}$ 翻转为 $\texttt{MM}$，然后追加 $\texttt{O}$ 形成 $\texttt{MMO}$。
4. 在输入第二个 $\texttt{M}$ 后，Bessie 得到字符串 $\texttt{MMOM}$。
5. 在输入最后一个 $\texttt{O}$ 后，字符串 $\texttt{MMOM}$ 翻转为 $\texttt{OOMO}$，然后追加 $\texttt{O}$ 形成 $\texttt{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$。

题目来源：Nick Wu