Curse your rival! Every year at the annual Rock Paper
Scissors tournament, you have made it to the final match. (Your
Rock technique is unmatched, and your Paper cuts to the bone!
Your Scissors need a little work, though.) But every year, he
defeats you, even though his moves appear entirely random! And
he claims to the press that he simply cannot be beaten. What is
Fortunately, you think you have figured it out. This year,
just before the tournament, you caught him visiting various
shamans around town. Aha! He is using the supernatural against
you! You figured two can play at this game. So you went and
visited a set of fortune-tellers, who have each used a Tarot
deck to predict a sequence that your rival will end up using,
sometime during the match.
However, your initial excitement has passed, and now you are
feeling a little silly. This cannot possibly work, right? In
the end it feels like you have paid good money for a
fraudulent, random set of predictions. Oh well; you might as
well keep an eye out for some of them during the match. But
which predictions will you use?
In the final match, you and your rival will play
$n$ rounds of Rock Paper
Scissors. In each round, your rival and you will both choose
one of the three options (Rock, Paper, or Scissors). Based on
your selections, a winner of the round will be determined
(exactly how is irrelevant to this problem).
Given the length of the final match and the various
predictions, sort them in order of how likely they are to
appear sometime during the match as a contiguous sequence of
options chosen by your rival, assuming he is choosing his
symbol in each round independently and uniformly at random.
The first line of input contains two integers $n$ ($1\leq n \leq 10^6$), the number of
rounds in the final match, and $s$ ($1
\leq s \leq 10$), the number of sequences. The remaining
$s$ lines each describe a
prediction, consisting of a string of characters ‘R’, ‘P’, and
‘S’. All predictions have the same
length, which is between $1$ and $n$ characters long, inclusive, and no
longer than $10^5$.
Display all of the predictions, sorted by decreasing
likelihood of appearance sometime during the final match. In
the case of tied predictions, display them in the same order as
in the input.
|Sample Input 1
||Sample Output 1
|Sample Input 2
||Sample Output 2