P6939 [ICPC 2017 WF] Tarot Sham Boast

诅咒你的对手！每年在年度石头剪刀布比赛中，你都进入了最后的决赛。（你的石头技巧无与伦比，你的纸张切割如刀！不过你的剪刀还需要一些改进。）但每年，他都击败了你，尽管他的动作看起来完全是随机的！而且他对媒体声称他根本无法被击败。他的秘密是什么？ 幸运的是，你认为你已经找到了答案。今年，就在比赛前，你抓到他在城里拜访各种萨满。啊哈！他在用超自然力量对付你！你想到了可以以其人之道还治其人之身。所以你去拜访了一些算命师，他们每个人都用塔罗牌预测了一些你对手将在比赛中某个时候使用的序列。 然而，你最初的兴奋已经过去，现在你觉得有点傻。这不可能奏效，对吧？最后你觉得自己花了不少钱买了一些虚假的、随机的预测。哦，好吧；你不妨在比赛中留意其中的一些。但你会使用哪些预测呢？ 在最后的比赛中，你和你的对手将进行 $n$ 轮石头剪刀布。在每一轮中，你的对手和你都将选择三种选项之一（石头、剪刀或布）。根据你们的选择，将决定该轮的胜者（具体如何决定与此问题无关）。 给定最后比赛的长度和各种预测，按它们在比赛中作为你对手选择的连续序列出现的可能性排序，假设他在每一轮中独立且均匀地随机选择他的符号。

输入的第一行包含两个整数 $n (1 \le n \le 10^{6})$，即最后比赛的轮数，以及 $s (1 \le s \le 10)$，即序列的数量。接下来的 $s$ 行每行描述一个预测，由字符 'R'、'P' 和 'S' 组成的字符串。所有预测的长度相同，长度在 $1$ 到 $n$ 个字符之间（包括 $n$），且不超过 $10^{5}$。

显示所有预测，按在最后比赛中出现的可能性从高到低排序。如果预测的可能性相同，则按输入中的顺序显示。

时间限制：2 秒，内存限制：512 MB。 题面翻译由 ChatGPT-4o 提供。