题目描述

你正在设计一款新游戏。游戏中有 $n$ 个场景，玩家可以按任意顺序游玩，但每个场景必须恰好游玩一次。

当玩家从一个场景切换到另一个场景时，游戏会播放一段专门制作的过渡视频，使所有场景看起来像一个完整故事。过渡视频只取决于两个场景的无序对：从场景 $a$ 切换到场景 $b$，与从场景 $b$ 切换到场景 $a$，播放的是同一段视频。

因此，一共需要制作

段不同的过渡视频。

每段视频可以是搞笑的（F），也可以是恐怖的（S）。连续看到太多同一类型的视频会很无聊，因此你希望完成所有视频的类型设计，使得：

无论玩家以何种顺序游玩这 $n$ 个场景，都不会连续看到超过

段同一类型的过渡视频。

你已经为至多 $\left\lfloor\dfrac n2\right\rfloor$ 段视频确定了类型。请为其余视频选择类型，使上述要求成立。

输入格式

第一行包含一个整数 $n$（$2\le n\le 24$），表示场景数量。

接下来 $n$ 行描述当前的部分方案，每行包含 $n$ 个字符。第 $i$ 行第 $j$ 个字符表示场景 $i$ 与场景 $j$ 之间的过渡视频：

• F：已经确定为搞笑视频；
• S：已经确定为恐怖视频；
• ?：尚未确定；
• .：$i=j$。

保证矩阵关于主对角线对称，即第 $i$ 行第 $j$ 个字符与第 $j$ 行第 $i$ 个字符相同。

保证至多有 $\left\lfloor\dfrac n2\right\rfloor$ 条无向边已经确定。由于每条边在矩阵中出现两次，因此输入中 F 和 S 字符的总数至多为 $2\left\lfloor\dfrac n2\right\rfloor$。

输出格式

输出 $n$ 行完整方案，每行包含 $n$ 个字符。

第 $i$ 行第 $j$ 个字符必须满足：

• 若 $i=j$，输出 .；
• 否则输出 F 或 S；
• 输入中原本为 ? 的位置必须替换为 F 或 S；
• 输入中已经确定的字符不得改变；
• 输出矩阵必须关于主对角线对称。

此外，对于 $n$ 个场景的任意排列，按该顺序游玩时，相邻场景间对应的视频序列中，连续相同类型的视频数量不得超过

若有多种方案，输出任意一种。可以证明，对所有满足约束的输入，答案一定存在。

样例 1

输入

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

输出

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

说明

允许连续出现的同类视频数量为

任意排列只会产生 $4$ 段过渡视频，因此只需保证不修改已经确定的类型即可。

样例 2

输入

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

输出

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

说明

例如排列

1 7 4 12 9 8 2 6 10 3 11 5

对应的视频类型序列为 SSSSSSSSSFS。虽然其中共有 $10$ 个 S，但最长连续段只有 $9$ 个，恰好不超过