Prefixes and Suffixes
Contest: Codeforces Round 527 (Div. 3)
Difficulty rating: 1700
Tags: strings

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!

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
ba
a
abab
a
aba
baba
ab
aba

Example output:
SPPSPSPS

Example input:
3
a
aa
aa
a

Example output:
PPSS

Editorial:
The first observation: if we will take two strings of length $$$n-1$$$ then we almost can restore the initial string. Why almost? Because there are two possible options: when the first string of length $$$n-1$$$ is a prefix and the second one is the suffix and vice versa.
Let's write a function check(pref, suf) which will check if the first string can be the prefix of the guessed string and the second one can be the suffix. After we write this function, we can run it two times (depending on the order of strings of length $$$n-1$$$) and find any suitable answer.
If the first string ($$$pref$$$) is the prefix and the second one ($$$suf$$$) is the suffix then the whole string $$$s = pref + suf_{n - 2}$$$ ($$$0$$$-indexed) where '+' is the concatenation of strings. Let's check if we have all prefixes and suffixes of this string in the input. We can easy do it with two nested loops and some boolean array which can say us if some string is already used or not. Firstly, let's iterate over the length of the prefix or suffix and inside let's find any string from the input matching to the current prefix or suffix. If we find all $$$2n - 2$$$ strings then the current string is one of the guessed and we can print the answer.