题目描述

冰封的世界可以看作是 $n$ 块初始时冷冻的冰川，这些冰川被编号为 $1 \sim n$。

探测器抵达后的 $m$ 秒，每秒都会探测到一块冰川融化。

当一块冰川第一次融化时，探测器返回 N，否则返回 Y。

你需要根据探测器按顺序返回的信息，给出字典序最小的冰川融化过程的编号序列。如果不存在这样的编号序列，请输出 No solution 报告无解。

输入格式

第一行两个整数 $n,m$。

接下来一行 $m$ 个字符（N 或 Y，不加分隔），表示探测器按顺序返回的结果。

输出格式

一行一个长度为 $m$ 的整数序列（空格分隔），表示字典序最小的冰川融化过程的编号序列，或输出 No solution 报告无解。

3 4
NYNY

1 1 2 1

5 3
YYY

No solution

5 7
NNNNNYN

No solution

提示

【样例 1 解释】

第 1 秒，1 号冰川融化，这是其首次融化，返回 N。

第 2 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1 秒融化过，返回 Y。

第 3 秒，2 号冰川融化，这是其首次融化，返回 N。

第 4 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1,2 秒融化过，返回 Y。

【数据范围】

对于 $100\%$ 的数据，$1 \le n,m \le 10^6$。

提示：本题开启捆绑测试。

$$\def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c} \textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& n,m\le 8 & 23 \r \textsf2& n,m\le 1000 & 25 \r \textsf3& 探测器返回结果只有一种字符 & 15 \r \textsf4& 保证有解 & 17 \r \textsf5& 无特殊限制 & 20 \r \end{array} $$

题目来源

项目	人员
idea	船酱魔王
data
check	EstasTonne
solution	船酱魔王