CF1949D Funny or Scary?

你正在设计一款新的电子游戏。它有 $n$ 个场景，玩家可以按任何顺序游玩，但每个场景只玩一次。当玩家从一个场景切换到另一个场景时，游戏会显示一个过渡视频，让玩家感觉这一切都是故事的一部分。该视频特定于一对场景，但不按其顺序，也就是说，从场景 $a$ 切换到场景 $b$ 时播放的视频与从场景 $b$ 切换到场景 $a$ 时播放的相同。因此，您需要创建 $\frac{n(n-1)}{2}$ 个不同的过渡视频，每对不同场景都有一个。 每个过渡视频可以是有趣的，也可以是恐怖的。连续看太多有趣的视频或太多恐怖的视频会很无聊。因此，你的目标是以这样一种方式创建视频：无论玩家以何种顺序处理场景，他们都不会连续看到超过 $\lceil\frac{3n}{4}\rceil$ 的相同类型的过渡视频。 您已经为最多 $\lfloor \frac{n}{2} \rfloor$ 个的过渡视频想出了主意，因此你已经知道这些视频是有趣还是可怕了。现在，你需要为所有剩余的过渡视频选择有趣或恐怖的视频，以满足上述要求。

第一行包含一个整数 $ n $ ( $ 2 \le n \le 24 $ ) ——游戏中场景的数量。 接下来的 $n$ 行描述部分过渡视频的计划。 每一行都包含 $n$ 个字符。第 $i$ 行的第 $j$ 个字符对应于第 $i$ 个和第 $j$ 个场景之间的转换视频。如果相应的过渡视频会很有趣，则为 $\texttt{F}$，如果相应的转换视频会很恐怖，则为 $\texttt{S}$。如果对应的转换视频仍然是未决定的，或者如果 $i＝j$，则为 $\texttt{?}$。 保证第 $j$ 行的第 $i$ 个字符和第 $i$ 行的第 $j$ 个字符对于所有 $i$ 和 $j$ 都是相同的。最多 $ \lfloor \frac{n}{2} \rfloor $（$n$ 除以 $2$，向下取整）个转换视频将已经被决定，换句话说，输入中最多 $2\lfloor \frac{n}{2} \rfloor $ 个字符将是 $\texttt{F}$ 或 $\texttt{S}$。

以与输入相同的格式输出描述完整过渡视频计划的 $n$ 行。每一行都必须包含 $n$ 个字符。如果相应的过渡视频是有趣的，第 $i$ 行的第 $j$ 个字符是 $\texttt{F}$，如果相应的转换视频是恐怖的，或者如果 $i＝j$，第 $i$ 行的第 $j$ 个字符是 $\texttt{S}$。 每个输入中的 $\texttt{?}$ 字符必须替换为 $\texttt{F}$ 或 $\texttt{S}$，并且输入时的所有 $\texttt{F}$ 或 $\texttt{S}$ 必须与输入时保持不变。它必须仍然保持第 $j$ 行的第 $i$ 个字符和第 $i$ 行的第 $j$ 个字符对于所有 $i$ 和 $j$ 都是相同的。 对于 $n$ 个场景的每一个排列，必须确保按此顺序播放与场景相对应的转换视频连续不超过相同类型的 $ \lceil \frac{3n}{4} \rceil $ （$3n$ 除以 $4$，向上取整）个视频。 如果有多个解决方案，请输出其中任何一个。保证对于满足该问题的所有输入均有解。

在第一个样例中： 我们允许连续出现 $\lceil \frac{3 \cdot 5}{4} \rceil = 4$ 个相同类型的转场视频，但对于这 $5$ 个场景的任意排列，玩家总共只会看到 $4$ 个转场视频，因此我们可以自由选择搞笑或恐怖类型。我们仍然必须遵守已经选择好的类型。 在第二个样例中： 在 $479001600$ 种可能的场景排列中，有一种是 $1, 7, 4, 12, 9, 8, 2, 6, 10, 3, 11, 5$。对于这个排列，玩家将得到以下转场视频序列：`SSSSSSSSSFS`。尽管这个序列总共有 $10$ 个恐怖转场视频，但连续出现的恐怖转场视频只有 $9$ 个，这也是最大允许数量（ $\lceil \frac{3 \cdot 12}{4} \rceil = 9$）。