题目描述

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 his secret?

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 \le n \le 10^{6}),$ the number of rounds in the final match, and $s (1 \le s \le 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.

题目大意

定义某字符串 $s$ 的出现概率为：随机敲 $n$ 个 R,P,S， $s$ 作为其子串出现的概率。

给出 $s$ 个长度为 $l$ 的只含 R,P,S 的字符串，请你按这 $l$ 个字符串的出现概率从大到小排序。若概率相等则按输入顺序排序。

$n\le 10^6,s\le 10,l\le 10^5$。

3 4
PP
RR
PS
SS

PS
PP
RR
SS

20 3
PRSPS
SSSSS
PPSPP

PRSPS
PPSPP
SSSSS

提示

Time limit: 2 s, Memory limit: 512 MB.