Problem Description

The frozen world can be considered as $n$ initially frozen glaciers, numbered from $1$ to $n$.

After the detector arrives, it will detect the melting of one glacier every second for $m$ seconds.

When a glacier melts for the first time, the detector returns N; otherwise, it returns Y.

You need to determine the lexicographically smallest sequence of glacier melting numbers based on the detector's sequential return information. If no such sequence exists, output No solution to indicate no solution.

Input Format

The first line contains two integers $n$ and $m$.

The next line contains $m$ characters (N or Y, without separators), representing the detector's sequential return results.

Output Format

Output one line containing an integer sequence of length $m$ (separated by spaces), representing the lexicographically smallest sequence of glacier melting numbers, or output No solution to indicate no solution.

Sample Input and Output

Sample Input #1

3 4
NYNY

Sample Output #1

1 1 2 1

Sample Input #2

5 3
YYY

Sample Output #2

No solution

Sample Input #3

5 7
NNNNNYN

Sample Output #3

No solution

Notes

[Sample 1 Explanation]

In the 1st second, Glacier 1 melts, which is its first melting, returning N.

In the 2nd second, Glacier 1 melts again, not its first melting, returning Y.

In the 3rd second, Glacier 2 melts, which is its first melting, returning N.

In the 4th second, Glacier 1 melts again, not its first melting, returning Y.

[Data Range]

For $100\%$ of the data, $1 \le n, m \le 10^6$.

Hint: This problem has 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& Detector returns only one type of character & 15 \r \textsf4& Guaranteed to have a solution & 17 \r \textsf5& No special constraints & 20 \r \end{array} $$

Problem Source

见题面 Input 部分

见题面 Output 部分