Fortune Teller Predictions

Every year at the annual Rock Paper Scissors tournament, you face a rival whose moves seem inexplicably random. However, your suspicions have been confirmed: he is using supernatural help! Before the match, you obtained a set of predictions from fortune-tellers using Tarot decks. Each prediction is a sequence composed of symbols from {R, P, S} (standing for Rock, Paper, and Scissors respectively).

In the final match of n rounds, both you and your rival will select one symbol per round independently and uniformly at random. Your rival’s sequence is random, with each round having probability \( \frac{1}{3} \) for each symbol. A predicted sequence of length \( m \) appears if it occurs as a contiguous subsequence in the rival's moves. Its probability of appearance is given by \[ P = 1 - \frac{A(n,m)}{3^n}, \] where \(A(n,m)\) is the number of sequences of length \( n \) that avoid the given predicted sequence.

Your task is to sort all the given predictions in descending order of the probability of their occurrence sometime during the match. In case of ties, sort them in lexicographical order (i.e. the usual dictionary order).

Notes: To compute the probability for a given prediction string \(S\) of length \( m \), you may simulate a dynamic programming process using an automaton (constructed by the KMP algorithm) that tracks the longest prefix of \(S\) matched thus far. Only sequences that avoid reaching the terminal state (i.e. a full match, state \(m\)) are counted.

inputFormat

The input is given as follows:

• The first line contains an integer n (\(1 \le n \le 1000\)), the number of rounds in the match.
• The second line contains an integer k (\(1 \le k \le 100\)), the number of predictions.
• Each of the next k lines contains a non-empty string consisting solely of the characters R, P, and S, representing a predicted contiguous sequence.

outputFormat

Output the k prediction strings sorted in descending order of their probability of appearing at least once in the rival's sequence. If two predictions have the same probability, output them in lexicographical order. Each prediction should be printed on a separate line.

sample

5
3
R
RP
RPS

R
RP
RPS