Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Префиксы и суффиксы
ограничение по времени на тест
2.0 с
ограничение по памяти на тест
512 МБ
ввод
стандартный ввод
вывод
стандартный вывод

Иван хочет сыграть с вами в игру. Он загадал какую-то строку $$$s$$$ длины $$$n$$$, состоящую только из строчных букв латинского алфавита.

Вы не знаете эту строку. Иван сообщил вам все ее несобственные префиксы и суффиксы (то есть префиксы и суффиксы всех длин от $$$1$$$ до $$$n-1$$$), но он не сказал вам, какие из сообщенных им строк являются префиксами, а какие — суффиксами.

Иван хочет, чтобы вы угадали, какие из заданных $$$2n-2$$$ строк являются префиксами, а какие — суффиксами. Бывают случаи, когда невозможно угадать строку, которую загадывал Иван (так как несколько разных строк могли иметь одинаковый набор префиксов и суффиксов), но Иван примет ваш ответ, если он будет совпадать с любой подходящей под ограничения строкой. Да начнется игра!

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — длину загаданной строки $$$s$$$.

Следующие $$$2n-2$$$ строк содержат префиксы и суффиксы, по одному в строке. Каждый из них является строкой длины от $$$1$$$ до $$$n-1$$$, состоящей только из строчных букв латинского алфавита. Они могут быть заданы в произвольном порядке.

Гарантируется, что во входных данных ровно по $$$2$$$ строки каждой длины от $$$1$$$ до $$$n-1$$$. Также гарантируется, что эти строки являются префиксами и суффиксами какой-то существующей строки длины $$$n$$$.

Выходные данные

Выведите одну строку длины $$$2n-2$$$ — строку, состоящую только из символов 'P' и 'S'. Количество символов 'P' должно быть равно количеству символов 'S'. $$$i$$$-й символ этой строки должен быть равен 'P', если $$$i$$$-я входная строка является префиксом, и 'S' иначе.

Если существует несколько возможных ответов, вы можете вывести любой.

Примеры
Входные данные
5
ba
a
abab
a
aba
baba
ab
aba
Выходные данные
SPPSPSPS
Входные данные
3
a
aa
aa
a
Выходные данные
PPSS
Входные данные
2
a
c
Выходные данные
PS
Примечание

Единственная строка, которую мог загадать Иван в первом тестовом примере, — «ababa».

Единственная строка, которую мог загадать Иван во втором тестовом примере, — «aaa». Ответы «SPSP», «SSPP» и «PSPS» также являются правильными.

В третем тестовом примере Иван мог загадать строку «ac» или же строку «ca». Ответ «SP» также является правильным.