Ivan 想和你玩一个游戏。他选择了一些长度为 $$$n$$$ 且仅由小写拉丁字母组成的字符串 $$$s$$$。
你不知道这个字符串。 Ivan 已经告诉你它所有不正确的前缀和后缀(即长度从 $$$1$$$ 到 $$$n-1$$$ 的前缀和后缀),但他没有告诉你哪些字符串是前缀,哪些是后缀。
Ivan 希望您猜测给定的 $$$2n-2$$$ 字符串中哪些是给定字符串的前缀,哪些是后缀。可能无法猜测 Ivan 选择的字符串(因为多个字符串可能给出相同的一组后缀和前缀),但如果至少有一个字符串与其一致,Ivan 将接受您的答案。让游戏开始吧!
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 猜测的字符串 $$$s$$$ 的长度。
接下来的 $$$2n-2$$$ 行包含前缀和后缀,每行一个。它们中的每一个都是长度从 $$$1$$$ 到 $$$n-1$$$ 且仅由小写拉丁字母组成的字符串。它们可以按任意顺序给出。
保证从 $$$1$$$ 到 $$$n-1$$$ 每个长度都恰好有 $$$2$$$ 字符串。还保证这些字符串是长度为 $$$n$$$ 的某个现有字符串的前缀和后缀。
输出
打印一个长度为 $$$2n-2$$$ 的字符串 — 该字符串仅包含字符“P”和“S”。字符“P”的数量应等于字符“S”的数量。如果输入字符串的第 $$$i$$$ 是前缀,则该字符串的第 $$$i$$$ 字符应为“P”,否则为“S”。
如果有多个可能的答案,您可以打印任何一个。
示例
输入 #1
5 ba a abab a aba baba ab aba
输出 #1
SPPSPSPS
输入 #2
3 a aa aa a
输出 #2
PPSS
输入 #3
2 a c
输出 #3
PS
注意
Ivan 在第一个示例中唯一能猜到的字符串是“ababa”。
Ivan 在第二个示例中唯一能猜到的字符串是“aaa”。答案“SPSP”、“SSPP”和“PSPS”也是可以接受的。
在第三个示例中,Ivan 可以猜测字符串“ac”或字符串“ca”。答案“SP”也是可以接受的。