你正在设计一款新电子游戏。游戏包含 $n$ 个场景，玩家可以以任意顺序游玩，但每个场景必须恰好游玩一次。当玩家从一个场景切换到另一个场景时，游戏会播放一段精心制作的转场视频，以增强故事的连贯性。这段视频对应一对场景，且与顺序无关；换句话说，从场景 $a$ 切换到场景 $b$ 时播放的视频，与从场景 $b$ 切换到场景 $a$ 时播放的视频是相同的。因此，你需要为每一对不同的场景制作 $\frac{n(n-1)}{2}$ 段不同的转场视频。

每段转场视频可以是“搞笑的”（funny）或“恐怖的”（scary）。连续观看太多的搞笑视频或太多的恐怖视频会让人感到乏味。因此，你的目标是制作这些视频，使得无论玩家以何种顺序游玩场景，他们连续看到的同类型转场视频都不会超过 $\lceil \frac{3n}{4} \rceil$ 段。

你已经构思了至多 $\lfloor \frac{n}{2} \rfloor$ 段转场视频，因此已经确定了它们是搞笑的还是恐怖的。现在你需要为所有其他转场视频选择类型，以满足上述要求。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 24$)，表示游戏中的场景数量。

接下来的 $n$ 行描述了转场视频的初步计划。每行包含 $n$ 个字符。第 $i$ 行的第 $j$ 个字符对应第 $i$ 个场景和第 $j$ 个场景之间的转场视频。如果该转场视频为搞笑的，则为 F；如果为恐怖的，则为 S；如果尚未决定，则为 ?；如果 $i = j$，则为 .。

保证对于所有 $i$ 和 $j$，第 $i$ 行的第 $j$ 个字符与第 $j$ 行的第 $i$ 个字符相同。保证输入中已确定的转场视频至多有 $\lfloor \frac{n}{2} \rfloor$ 段，即输入中 F 或 S 的总数至多为 $2\lfloor \frac{n}{2} \rfloor$。

输出格式

输出 $n$ 行，描述完整的转场视频计划，格式与输入相同。每行必须包含 $n$ 个字符。第 $i$ 行的第 $j$ 个字符必须为 F（如果该转场视频为搞笑的）、S（如果为恐怖的）或 .（如果 $i = j$）。

输入中的每个 ? 字符必须替换为 F 或 S，其他字符必须保持不变。对于所有 $i$ 和 $j$，第 $i$ 行的第 $j$ 个字符与第 $j$ 行的第 $i$ 个字符必须相同。

对于 $n$ 个场景的每一种排列，按此顺序游玩场景时，连续出现的同类型转场视频数量不得超过 $\lceil \frac{3n}{4} \rceil$。

如果存在多种解，输出其中任意一种即可。可以证明，对于所有满足本题约束的输入，解总是存在的。

样例

样例输入 1

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

样例输出 1

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

说明 1

我们被允许连续观看至多 $\lceil \frac{3 \cdot 5}{4} \rceil = 4$ 段同类型的转场视频。由于 5 个场景的任意排列中，玩家总共只会看到 4 段转场视频，因此我们可以自由选择搞笑或恐怖类型，只需遵守已确定的类型即可。

样例输入 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.

说明 2

场景的 $479001600$ 种排列之一是 1, 7, 4, 12, 9, 8, 2, 6, 10, 3, 11, 5。对于该排列，玩家将获得以下转场视频序列：SSSSSSSSSFS。尽管该序列总共有 10 段恐怖转场视频，但其中连续的恐怖转场视频只有 9 段，这符合最大允许数量（$\lceil \frac{3 \cdot 12}{4} \rceil = 9$）。