「NnOI R2-T2」Glaciaxion

题目描述

冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川,这些冰川被编号为 $1 \sim n$。 探测器抵达后的 $ m $ 秒,每秒都会探测到一块冰川融化。 当一块冰川第一次融化时,探测器返回 ```N```,否则返回 ```Y```。 你需要根据探测器按顺序返回的信息,给出**字典序最小**的冰川融化过程的编号序列。如果不存在这样的编号序列,请输出 ```No solution``` 报告无解。

输入输出格式

输入格式


第一行两个整数 $ n,m $。 接下来一行 $ m $ 个字符(`N` 或 `Y`,不加分隔),表示探测器按顺序返回的结果。

输出格式


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

输入输出样例

输入样例 #1

3 4
NYNY

输出样例 #1

1 1 2 1

输入样例 #2

5 3
YYY

输出样例 #2

No solution

输入样例 #3

5 7
NNNNNYN

输出样例 #3

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 | 船酱魔王 |