D. 有趣还是恐怖？

单个测试点时间限制： $2$ 秒 单个测试点内存限制： $256$ 兆字节

你正在设计一款新的电子游戏。游戏中有 $n$ 个剧情关卡，玩家可以以任意顺序游玩，但每个关卡必须恰好游玩一次。当玩家从一个关卡切换到另一个关卡时，游戏会播放一段精心制作的过渡动画，让整体体验像是一个完整的故事。

这段动画只与一对关卡有关，与顺序无关。也就是说，从关卡 $a$ 切换到关卡 $b$ 的动画，与从 $b$ 切换到 $a$ 的动画是完全相同的。因此，你一共需要制作 $\dfrac{n(n-1)}{2}$ 段不同的过渡动画，每一段对应一对不同的关卡。

每段过渡动画可以是有趣（Funny，记为 F）或恐怖（Scary，记为 S）。连续看到太多同类动画会让玩家感到乏味。因此你的目标是： 无论玩家以何种顺序游玩关卡，都不会连续出现超过 $\boldsymbol{\lceil\dfrac{3n}{4}\rceil}$ 段同类过渡动画。

你已经为至多 $\boldsymbol{\lfloor\dfrac{n}{2}\rfloor}$ 段过渡动画确定了类型，剩下的尚未决定。你需要为所有未确定的动画选择 F 或 S，使得上述限制被满足。

输入格式

第一行一个整数 $n$ （ $2\le n\le 24$ ），表示游戏中的关卡数量。

接下来 $n$ 行，每行 $n$ 个字符，表示已有的过渡动画方案：

第 $i$ 行第 $j$ 个字符表示关卡 $i$ 与关卡 $j$ 之间的动画；
F 表示有趣，S 表示恐怖，? 表示未决定；
. 当且仅当 $i=j$ 。

保证输入是对称的：第 $i$ 行第 $j$ 个字符与第 $j$ 行第 $i$ 个字符相同。保证已经确定的动画数量不超过 $\boldsymbol{\lfloor\dfrac{n}{2}\rfloor}$ 。

输出格式

输出 $n$ 行，格式与输入相同：

所有 ? 必须替换为 F 或 S；
原有 .、F、S 保持不变；
矩阵仍然对称；
对关卡的任意排列，对应的连续同类动画长度不超过 $\boldsymbol{\lceil\dfrac{3n}{4}\rceil}$ 。

题目保证解一定存在，输出任意合法解即可。

样例输入 1

5
.?F??
?.???
F?.S?
??S.?
????.

样例输出 1

.FFFF
F.FFF
FF.SF
FFS.F
FFFF.

样例输入 2

12
.???????????
?.??????????
??.?????????
???.????????
????.???????
?????.??????
??????.?????
???????.????
????????.???
?????????.??
??????????.?
???????????.

样例输出 2

.SSSFFSSSSFS
S.SFFSFSFFFS
SS.SFFFSSSFS
SFS.FFSSSSFS
FFFF.FFFFFSF
FSFFF.SFFSFF
SFFSFS.SSSFS
SSSSFFS.SSFS
SFSSFFSS.SFS
SFSSFSSSS.FS
FFFFSFFFFF.F
SSSSFFSSSSF.

样例说明

第一个样例中，允许的最长连续同类长度为 $\lceil\dfrac{3\cdot 5}{4}\rceil=4$ 。而任意排列只有 $4$ 段过渡动画，因此只要满足已有设定即可自由填充。

第二个样例中，允许最长连续同类长度为 $\lceil\dfrac{3\cdot 12}{4}\rceil=9$ 。某个排列对应的动画序列为 SSSSSSSSSFS，最长连续一段为 $9$ ，恰好合法。

#CF1949D. 有趣还是恐怖？

有趣还是恐怖？