Prefixes and Suffixes

# 题目描述 Ivan挑了几个长度为$n$的小写英文字符串。 但是你不知道Ivan挑的是什么字符串。Ivan会给你这些字符串的前缀和后缀，但是你不知道哪个是前缀，哪个是后缀。 你的任务是猜出他给你的$2n-2$个字符串中哪个是前缀，哪个是后缀。猜出他挑的任意一个字符串，并且回答与之一致即可通过。 PS：在Ivan给你的某个字符串中，如果前面有一个与之相同并且你判了它为$P$，那么你只能判它为$S$。 # 输入输出格式 ## 输入格式 第1行是所猜字符串的长度$n$。 接下来$2n-2$行是Ivang给你的前缀或后缀。 数据保证：一定有2个长度为$1,2,...,n-1$的字符串。 ## 输出格式 输出一个长度为$2n-2$的字符串。第$i$个字符表示你对第$i$个前缀或后缀的判断。 第$i$个字符是$P$，说明你判断其为前缀；若是$S$，说明你判断其为后缀。

Ivan wants to play a game with you. He picked some string $ s $ of length $ n $ consisting only of lowercase Latin letters. You don't know this string. Ivan has informed you about all its improper prefixes and suffixes (i.e. prefixes and suffixes of lengths from $ 1 $ to $ n-1 $ ), but he didn't tell you which strings are prefixes and which are suffixes. Ivan wants you to guess which of the given $ 2n-2 $ strings are prefixes of the given string and which are suffixes. It may be impossible to guess the string Ivan picked (since multiple strings may give the same set of suffixes and prefixes), but Ivan will accept your answer if there is at least one string that is consistent with it. Let the game begin!

The first line of the input contains one integer number $ n $ ( $ 2 \le n \le 100 $ ) — the length of the guessed string $ s $ . The next $ 2n-2 $ lines are contain prefixes and suffixes, one per line. Each of them is the string of length from $ 1 $ to $ n-1 $ consisting only of lowercase Latin letters. They can be given in arbitrary order. It is guaranteed that there are exactly $ 2 $ strings of each length from $ 1 $ to $ n-1 $ . It is also guaranteed that these strings are prefixes and suffixes of some existing string of length $ n $ .

Print one string of length $ 2n-2 $ — the string consisting only of characters 'P' and 'S'. The number of characters 'P' should be equal to the number of characters 'S'. The $ i $ -th character of this string should be 'P' if the $ i $ -th of the input strings is the prefix and 'S' otherwise. If there are several possible answers, you can print any.

5
ba
a
abab
a
aba
baba
ab
aba

SPPSPSPS

3
a
aa
aa
a

PPSS

2
a
c

PS

The only string which Ivan can guess in the first example is "ababa". The only string which Ivan can guess in the second example is "aaa". Answers "SPSP", "SSPP" and "PSPS" are also acceptable. In the third example Ivan can guess the string "ac" or the string "ca". The answer "SP" is also acceptable.