题目描述

塔尖信奥的电脑中了病毒。

现在你要在键盘上输入一个字符串 $S$，长度为 $n$，其中每个字符都是 M 或 O。

键盘只有两个按键：M 和 O，但存在如下异常规则：

• 按下 M：直接在当前字符串末尾添加一个 M
• 按下 O：会先将当前字符串中的所有字符翻转（M 变成 O，O 变成 M），然后在末尾添加一个 O

初始时字符串为空。

现在给定目标字符串 $S$，判断是否存在一种按键序列，使得最终得到的字符串恰好为 $S$。

此外给定参数 $k$：

• 若 $k=0$，只需判断是否可行
• 若 $k=1$，还需输出一种可行的按键序列

输入格式

本题有多组数据

第一行两个整数 $T,k$。接下来是 $T$ 组数据，每一组数据：

• 第一行一个整数 $n$。
• 第二行一个长度为 $n$ 的字符串 $S$。

输出格式

对于每组数据：

• 若无法构造，输出一行 NO
• 否则输出一行 YES
• 若 $k=1$，再输出一行长度为 $n$ 的字符串，表示一种可行的按键序列。输出任意一种合法的方案均可。

2 0
3
MOO
5
OOMOO

YES
YES

2 1
3
MOO
5
OOMOO

YES
OMO
YES
MOOMO

提示

样例 2 解释

例如按键序列 MOOMO 的执行过程如下：

• 初始为空字符串
• 按 M → M
• 按 O → 翻转 M → O，再加 O → OO
• 按 O → 翻转 OO → MM，再加 O → MMO
• 按 M → MMOM
• 按 O → 翻转 MMOM → OOMO，再加 O → OOMOO

最终得到目标字符串。

数据范围

对于 $100$ 的数据：

• $1 \le T \le 10^4$
• $1 \le n \le 2 \times 10^5$
• 所有测试数据的 $n$ 之和不超过 $4 \times 10^5$