Melting Glaciers

The frozen world consists of \( n \) glaciers, numbered from 1 to \( n \). When a detector arrives, it observes that one glacier melts per second over \( m \) seconds.

For each second, when a glacier melts for the first time, the detector reports N; if the glacier has melted before, it reports Y. Based on the sequence of reports, you are required to determine the lexicographically smallest possible sequence of glacier numbers representing the melting process. If no valid sequence exists, output No solution.

Note that in lexicographical order, a sequence \( a_1,a_2,\ldots,a_m \) is considered smaller than \( b_1,b_2,\ldots,b_m \) if there exists an index \( i \) such that \( a_j = b_j \) for all \( j < i \) and \( a_i < b_i \).

The melting process must obey the following rules:

• If the report is N, the corresponding glacier must be melting for the first time (i.e. it has not melted before).
• If the report is Y, the corresponding glacier must have melted previously.

Your task is to reconstruct the melting sequence with the minimum lexicographical order among all valid sequences.

inputFormat

The first line contains two integers \( n \) and \( m \) \((1 \leq n, m \leq 10^5)\), representing the number of glaciers and the number of seconds (or events), respectively.

The second line contains a string of length \( m \) composed of characters N and Y representing the detector's report at each second.

outputFormat

If a valid melting process exists, output the lexicographically smallest sequence of \( m \) glacier numbers (separated by spaces) that corresponds to the reports. Otherwise, output No solution.

sample

3 5
NYYNN

1 1 1 2 3