String Guessing

Interview

Time limit2sMemory limit512 MB

Summary

Given all 2N-2 prefixes and suffixes of a hidden string, recover the string and label each input line as prefix or suffix in order.

Level: Medium5 of 10
Topics: String, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

There is a string S of length N. S consists only of lowercase English letters.

We want to reconstruct the original string S from all prefixes and suffixes of S whose length is at most N-1. Given all prefixes and suffixes of S, write a program that finds the original string S.

Input

The first line gives the length N of the string S (2 ≤ N ≤ 100). The following 2N-2 lines give the prefixes and suffixes of S, one per line. Since all prefixes and suffixes are given, the number of strings of length i (1 ≤ i ≤ N-1) is always 2.

Output

On the first line, print the string S that can be built from the prefixes and suffixes given as input.

On the second line, print 'P' if the input string is a prefix and 'S' if it is a suffix, in the order the strings were given.

Hint

A prefix of a string S is a substring of S that starts at the first character, and a suffix is one that ends at the last character.

For S = "hello", the prefixes are the following 5 strings.

h
he
hel
hell
hello

The suffixes are as follows.

o
lo
llo
ello
hello

Examples3

Example 1

Input

5
ba
a
abab
a
aba
baba
ab
aba

Expected output

ababa
SPPSPSPS

Example 2
Input
```
3
a
aa
aa
a
```
Expected output
```
aaa
PPSS
```
Example 3
Input
```
2
a
c
```
Expected output
```
ac
PS
```