#6480. 「ICPC World Finals 2017」弄虚作假的塔罗占卜 Tarot Sham Boast

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

请诅咒你的对手!在每年的年度石头剪刀布锦标赛上,你总是能进总决赛。(你的石头技巧无与伦比,你的布震撼人心!不过你的剪刀需要练练)但是每年,你的对手总是能打败你,即使他的操作看上去是完全是随机的!而且他发布新闻声称他无可匹敌。他的秘诀是什么?

幸运的是,你认为你已经找到了。就在今年,锦标赛之前的时候,你发现他拜访了城里的许多萨满。啊哈!原来他在使用超自然力量对付你!你觉得这次可以好好玩一玩了。所以你拜访了一群算命师,他们用塔罗牌帮你预测了对手在比赛中会使用的操作序列。

然而,你最初的兴奋已经过去了,你现在感觉自己有点智障。这怎么可能赢?最后你才发现你已经对这种随机预测的欺诈行为付出了许多钱。好吧,你可能会在比赛中留意其中一些预测。但是用哪些预测好呢?

在总决赛中,你和你的对手将玩 n 轮石头剪刀布。每一轮中,你和你的对手会从三种选择(石头、剪刀、布)中选择一个操作。根据你们的选择来确定每一轮的胜利者(实际上与本题没太大关系)。

给定总决赛的长度和一些预测,请你按照在总决赛中作为你对手操作的一个连续子序列出现的可能性排序它们,这里假设对方每一轮的选择是独立随机的。

输入格式

第一行包含两个整数 n (1 \leq n \leq 10^6) s (1 \leq s \leq 10) ,分别表示总决赛的轮数和序列的数量。

接下来 s 行,每行描述一种预测,包含一个由 R, P, S 组成的字符串。所有的预测拥有相同的长度,长度在 1 n 之间(含边界),且不会超过 10^5

输出格式

输出按照在总决赛出现的可能性降序输出所有的预测。对于可能性相同的预测,按照他们在输入中的顺序输出。

样例

样例输入 1

3 4
PP
RR
PS
SS

样例输出 1

PS
PP
RR
SS

样例输入 2

20 3
PRSPS
SSSSS
PPSPP

样例输出 2

PRSPS
PPSPP
SSSSS