Иван хочет сыграть с вами в игру. Он загадал какую-то строку \(s\) длины \(n\), состоящую только из строчных букв латинского алфавита.
Вы не знаете эту строку. Иван сообщил вам все ее несобственные префиксы и суффиксы (то есть префиксы и суффиксы всех длин от \(1\) до \(n-1\)), но он не сказал вам, какие из сообщенных им строк являются префиксами, а какие — суффиксами.
Иван хочет, чтобы вы угадали, какие из заданных \(2n-2\) строк являются префиксами, а какие — суффиксами. Бывают случаи, когда невозможно угадать строку, которую загадывал Иван (так как несколько разных строк могли иметь одинаковый набор префиксов и суффиксов), но Иван примет ваш ответ, если он будет совпадать с любой подходящей под ограничения строкой. Да начнется игра!
Выходные данные
Выведите одну строку длины \(2n-2\) — строку, состоящую только из символов 'P' и 'S'. Количество символов 'P' должно быть равно количеству символов 'S'. \(i\)-й символ этой строки должен быть равен 'P', если \(i\)-я входная строка является префиксом, и 'S' иначе.
Если существует несколько возможных ответов, вы можете вывести любой.
Примечание
Единственная строка, которую мог загадать Иван в первом тестовом примере, — «ababa».
Единственная строка, которую мог загадать Иван во втором тестовом примере, — «aaa». Ответы «SPSP», «SSPP» и «PSPS» также являются правильными.
В третем тестовом примере Иван мог загадать строку «ac» или же строку «ca». Ответ «SP» также является правильным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
ba
a
abab
a
aba
baba
ab
aba
|
SPPSPSPS
|
|
2
|
3
a
aa
aa
a
|
PPSS
|
|
3
|
2
a
c
|
PS
|