311200: CF1949D. Funny or Scary?

D. Funny or Scary?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are designing a new video game. It has $n$ scenarios, which the player may play in any order, but each scenario must be played exactly once. When a player switches from a scenario to another scenario, the game shows a specially crafted transition video to make it all feel part of one big story. This video is specific to a pair of scenarios, but not to their order, in other words, the video playing when switching from scenario $a$ to scenario $b$ is the same as the video playing when switching from scenario $b$ to scenario $a$. Therefore, you need to create $\frac{n(n-1)}{2}$ different transition videos, one for each possible pair of different scenarios.

Each transition video can be either funny or scary. It is boring to see too many funny videos or too many scary videos in a row. Therefore, your goal is to create the videos in such a way that no matter in which order does the player approach the scenarios, they will never see more than $\lceil \frac{3n}{4} \rceil$ transition videos of the same type in a row.

You have already come up with ideas for at most $\lfloor \frac{n}{2} \rfloor$ of the transition videos, and therefore already know if those will be funny or scary. Now you need to choose funny or scary for all other transition videos in such a way that the above requirement is satisfied.

Input

The first line contains a single integer $n$ ($2 \le n \le 24$) — the number of scenarios in the game.

The next $n$ lines describe the partial transition video plan. Each of those lines contains $n$ characters. The $j$-th character of the $i$-th line corresponds to the transition video between the $i$-th and the $j$-th scenarios. It will be F if the corresponding transition video will be funny, S if the corresponding transition video will be scary, ? if the corresponding transition video is still undecided, or . if $i=j$.

It is guaranteed that the $i$-th character of the $j$-th line and the $j$-th character of the $i$-th line will be the same for all $i$ and $j$. It is guaranteed that at most $\lfloor \frac{n}{2} \rfloor$ ($n$ divided by 2, rounded down) transition videos will already be decided, in other words, that at most $2\lfloor \frac{n}{2} \rfloor$ characters in the input will be F or S.

Output

Print $n$ lines describing the full transition video plan in the same format as the input. Each of those lines must contain $n$ characters. The $j$-th character of the $i$-th line must be F if the corresponding transition video is funny, S if the corresponding transition video is scary, or . if $i=j$.

Each ? character from the input must be replaced with either F or S, and all other characters from the input must remain unchanged. It must still hold that the $i$-th character of the $j$-th line and the $j$-th character of the $i$-th line are the same for all $i$ and $j$.

For each permutation of the $n$ scenarios, it must hold that the transition videos corresponding to playing the scenarios in this order do not have more than $\lceil \frac{3n}{4} \rceil$ ($3n$ divided by 4, rounded up) videos of the same type consecutively.

If there are multiple solutions, print any of them. It can be proven that for all inputs satisfying the constraints of this problem a solution always exists.

ExamplesInput

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

Output

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

Input

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

Output

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

Note

In the first sample: We are allowed $\lceil \frac{3\cdot 5}{4} \rceil=4$ transition videos of the same type in a row, but for any permutation of the 5 scenarios the player will see only 4 transition videos in total, therefore we can choose funny or scary freely. We must still respect the already chosen types.

In the second sample: One of the 479001600 possible permutations of scenarios is 1, 7, 4, 12, 9, 8, 2, 6, 10, 3, 11, 5. The player will get the following sequence of transition videos for this permutation: SSSSSSSSSFS. Even though this sequence has 10 scary transition videos in total, it has only 9 scary transition videos in a row, which is the maximum allowed amount ($\lceil \frac{3\cdot 12}{4} \rceil=9$).

题目大意：
你正在设计一个新的视频游戏，它有n个场景，玩家可以以任何顺序玩这些场景，但每个场景必须玩一次。当玩家从一个场景切换到另一个场景时，游戏会显示一个特别制作的过渡视频，使其感觉像是整个大故事的一部分。这个视频是特定于一对场景的，但与它们的顺序无关，换句话说，从场景a切换到场景b的视频与从场景b切换到场景a的视频是相同的。因此，你需要创建n(n-1)/2个不同的过渡视频，每个可能的场景对都有一个。

每个过渡视频可以是【有趣】或【恐怖】。连续看太多有趣或恐怖的视频会很无聊。因此，你的目标是以这样的方式创建视频，无论玩家以何种顺序接近场景，他们都不会看到超过⌈3n/4⌉个连续的同一类型的过渡视频。

你已经为最多⌊n/2⌋个过渡视频想出了点子，因此已经知道这些视频将是【有趣】还是【恐怖】。现在你需要为所有其他过渡视频选择【有趣】或【恐怖】，以使上述要求得到满足。

输入输出数据格式：
输入：
第一行包含一个整数n（2≤n≤24）——游戏中的场景数。
接下来n行描述部分过渡视频计划。每行包含n个字符。第i行第j个字符对应于第i个和第j个场景之间的过渡视频。如果相应的过渡视频是有趣的，则为【F】；如果相应的过渡视频是恐怖的，则为【S】；如果相应的过渡视频尚未决定，则为【?】；如果i=j，则为【.】。
保证第i行第j个字符和第j行第i个字符对于所有的i和j都是相同的。保证最多有⌊n/2⌋（n除以2，向下取整）个过渡视频已经决定，换句话说，输入中最多有2⌊n/2⌋个字符是【F】或【S】。

输出：
打印n行，以与输入相同的格式描述完整的过渡视频计划。每行必须包含n个字符。第i行第j个字符如果是相应的过渡视频是有趣的，则为【F】；如果相应的过渡视频是恐怖的，则为【S】；如果i=j，则为【.】。
输入中的每个【?】字符必须替换为【F】或【S】，输入中的所有其他字符必须保持不变。对于所有的i和j，第i行第j个字符和第j行第i个字符必须相同。
对于n个场景的每个排列，必须保持相应于按此顺序播放场景的过渡视频没有超过⌈3n/4⌉（3n除以4，向上取整）个连续的同一类型的视频。
如果有多个解决方案，打印其中任何一个。可以证明，对于满足此问题约束的所有输入，总是存在解决方案。题目大意： 你正在设计一个新的视频游戏，它有n个场景，玩家可以以任何顺序玩这些场景，但每个场景必须玩一次。当玩家从一个场景切换到另一个场景时，游戏会显示一个特别制作的过渡视频，使其感觉像是整个大故事的一部分。这个视频是特定于一对场景的，但与它们的顺序无关，换句话说，从场景a切换到场景b的视频与从场景b切换到场景a的视频是相同的。因此，你需要创建n(n-1)/2个不同的过渡视频，每个可能的场景对都有一个。 每个过渡视频可以是【有趣】或【恐怖】。连续看太多有趣或恐怖的视频会很无聊。因此，你的目标是以这样的方式创建视频，无论玩家以何种顺序接近场景，他们都不会看到超过⌈3n/4⌉个连续的同一类型的过渡视频。 你已经为最多⌊n/2⌋个过渡视频想出了点子，因此已经知道这些视频将是【有趣】还是【恐怖】。现在你需要为所有其他过渡视频选择【有趣】或【恐怖】，以使上述要求得到满足。 输入输出数据格式： 输入： 第一行包含一个整数n（2≤n≤24）——游戏中的场景数。 接下来n行描述部分过渡视频计划。每行包含n个字符。第i行第j个字符对应于第i个和第j个场景之间的过渡视频。如果相应的过渡视频是有趣的，则为【F】；如果相应的过渡视频是恐怖的，则为【S】；如果相应的过渡视频尚未决定，则为【?】；如果i=j，则为【.】。 保证第i行第j个字符和第j行第i个字符对于所有的i和j都是相同的。保证最多有⌊n/2⌋（n除以2，向下取整）个过渡视频已经决定，换句话说，输入中最多有2⌊n/2⌋个字符是【F】或【S】。 输出： 打印n行，以与输入相同的格式描述完整的过渡视频计划。每行必须包含n个字符。第i行第j个字符如果是相应的过渡视频是有趣的，则为【F】；如果相应的过渡视频是恐怖的，则为【S】；如果i=j，则为【.】。 输入中的每个【?】字符必须替换为【F】或【S】，输入中的所有其他字符必须保持不变。对于所有的i和j，第i行第j个字符和第j行第i个字符必须相同。 对于n个场景的每个排列，必须保持相应于按此顺序播放场景的过渡视频没有超过⌈3n/4⌉（3n除以4，向上取整）个连续的同一类型的视频。 如果有多个解决方案，打印其中任何一个。可以证明，对于满足此问题约束的所有输入，总是存在解决方案。