P9570 "NnOI R2-T2" Glaciaxion

The frozen world can be seen as $n$ glaciers that are frozen at the beginning. These glaciers are numbered from $1$ to $n$. In the $m$ seconds after the probe arrives, each second it will detect that one glacier melts. When a glacier melts for the first time, the probe returns `N`; otherwise it returns `Y`. You need to output the **lexicographically smallest** sequence of glacier indices that matches the probe’s returned information in order. If no such sequence exists, output `No solution`.

The first line contains two integers $n, m$. The next line contains $m$ characters (`N` or `Y`, without separators), representing the probe’s returned results in order.

Output one line with an integer sequence of length $m$ (separated by spaces), representing the **lexicographically smallest** sequence of glacier indices for the melting process, or output `No solution`.

**[Sample 1 Explanation]** At second 1, glacier 1 melts. This is its first time melting, so it returns `N`. At second 2, glacier 1 melts. This is not its first time melting, because it has already melted at second 1, so it returns `Y`. At second 3, glacier 2 melts. This is its first time melting, so it returns `N`. At second 4, glacier 1 melts. This is not its first time melting, because it has already melted at seconds 1 and 2, so it returns `Y`. **[Constraints]** For $100\%$ of the testdata, $1 \le n, m \le 10^6$. **Hint: This problem uses bundled tests.** $$ \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& The probe’s returned results contain only one kind of character & 15 \r \textsf4& A solution is guaranteed & 17 \r \textsf5& No special constraints & 20 \r \end{array} $$ ### Source | Item | People | |:-:|:-:| | idea | Chuanjiang Mowang | | data | Chuanjiang Mowang | | check | EstasTonne | | solution | Chuanjiang Mowang | Translated by ChatGPT 5