Tarot Sham Boast

Every year you reach the final of the rock paper scissors tournament, and every year the same rival beats you. His moves look completely random, yet he tells the press that nobody can beat him.

This year, just before the tournament, you caught him visiting shamans all over town. So you went and visited a whole row of fortune tellers yourself. Each of them laid out a Tarot deck and handed you one sequence of moves that your rival will play at some point during the match.

The predictions are probably worthless. You paid for them anyway, so you may as well watch for some of them during the match. Which ones should you watch?

The final match runs for $n$ rounds. In each round your rival picks Rock, Paper, or Scissors uniformly at random, independently of every other round. A prediction appears during the match if it occurs as a contiguous block of the moves your rival picked. Sort the predictions by the probability that they appear, from most likely to least likely.

The first line contains two integers $n$ ($1 \le n \le 10^6$), the number of rounds in the final match, and $s$ ($1 \le s \le 10$), the number of predictions.

Each of the next $s$ lines contains one prediction, a string over the characters R (Rock), P (Paper), and S (Scissors). All predictions have the same length. That length is at least 1, at most $n$, and at most $10^5$.

Print the $s$ predictions, one per line, sorted by decreasing probability that the prediction appears during the match. Print predictions of equal probability in the order they were given in the input.