Problem Description

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.

Input Format

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 Format

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.

3 4
NYNY

1 1 2 1

5 3
YYY

No solution

5 7
NNNNNYN

No solution

Hint

[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
check	EstasTonne
solution	Chuanjiang Mowang

Translated by ChatGPT 5