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