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

The first line of the input contains one integer number n (2 ≤ n ≤ 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

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.

Examples

Input


5
ba
a
abab
a
aba
baba
ab
aba


Output


SPPSPSPS


Input


3
a
aa
aa
a


Output


PPSS


Input


2
a
c


Output


PS

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.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class codeforces
{
    static int M = 1_000_000_007;
    static int INF = 2_000_000_000;
    static final FastScanner fs = new FastScanner();

    //variable

    public static void main(String[] args) throws IOException {

        int n = fs.nextInt();
        String[][] s = new String[n-1][2];
        int[][] ass = new int[n-1][2];

        char[] ans = new char[2*n-2];
        for(int i=0;i<2*n-2;i++) {
            String str = fs.next();
            int m = str.length()-1;
            if(s[m][0] == null){
                s[m][0] = str;
                ass[m][0] = i;
            }
            else {
                s[m][1] = str;
                ass[m][1] = i;
            }
        }
//        for(int i=0;i<n-1;i++) {
//            System.out.println(s[i][0]+" "+s[i][1]);
//        }
        String pre = s[n-2][0];
        String suf = s[n-2][1];

        for(int j=0;j<2;j++) {
            boolean ok = true;
            boolean chk[] = new boolean[2*n-2];
            //for(int i=0;i<2*n-2;i++) ans[i] = '?';
            String temp = pre;
            pre = suf;
            suf = temp;
            for (int i = 0; i < n - 1; i++) {
                if (s[i][0].equals(pre.substring(0, i + 1))) {
                    ans[ass[i][0]] = 'P';
                    chk[ass[i][0]] = true;
                } else if (s[i][1].equals(pre.substring(0, i + 1))) {
                    ans[ass[i][1]] = 'P';
                    chk[ass[i][1]] = true;
                }
            }
            
            for (int i = 0; i < n - 1; i++) {

                if (s[i][0].equals(suf.substring(n - 2 - i)) && !chk[ass[i][0]]) {
                    ans[ass[i][0]] = 'S';
                    chk[ass[i][0]] = true;
                } else if (s[i][1].equals(suf.substring(n - 2 - i))) {
                    ans[ass[i][1]] = 'S';
                    chk[ass[i][1]] = true;
                }
            }
            for(char c:ans) if(c != 'S' && c != 'P') ok = false;
            if(ok) {
                System.out.println(new String(ans));
                break;
            }
        }

    }
    /*
4
o
oy
yy
yyy
oyy
y
*/

    //class

    //function
    public static class Flower implements Comparable<Flower>{
        int h,tb,tw;
        Flower(int h, int tb, int tw) {
            this.h = h;
            this.tb = tb;
            this.tw = tw;
        }

        @Override
        public int compareTo(Flower o) {
            return Integer.compare(this.h,o.h);
        }
    }
    // Template
    static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }

    static int gcd(int a, int b) {
        if(a==0) return b;

        return gcd(b%a,a);
    }
    static void premutation(int n, ArrayList<Integer> arr,boolean[] chosen) {
        if(arr.size() == n) {

        }else {
            for(int i=1; i<=n; i++) {
                if(chosen[i]) continue;
                arr.add(i);
                chosen[i] = true;
                premutation(n,arr,chosen);
                arr.remove(i);
                chosen[i] = false;
            }
        }
    }
    static boolean isPalindrome(char[] c) {
        int n = c.length;
        for(int i=0; i<n/2; i++) {
            if(c[i] != c[n-i-1]) return false;
        }
        return true;
    }

    static long nCk(int n, int k) {
        return (modMult(fact(n),fastexp(modMult(fact(n-k),fact(k)),M-2)));
    }

    static long fact (long n) {

        long fact =1;
        for(int i=1; i<=n; i++) {
            fact = modMult(fact,i);
        }
        return fact%M;
    }

    static int modMult(long a,long b) {
        return (int) (a*b%M);
    }
    static int negMult(long a,long b) {
        return (int)((a*b)%M + M)%M;
    }
    static long fastexp(long x, int y){
        if(y==1) return x;

        long ans = fastexp(x,y/2);
        if(y%2 == 0) return modMult(ans,ans);
        else return modMult(ans,modMult(ans,x));
    }

    static final Random random = new Random();

    static void ruffleSort(int[] arr)
    {
        int n = arr.length;
        for(int i=0; i<n; i++)
        {
            int j = random.nextInt(n),temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        Arrays.sort(arr);
    }


    public static class Pairs implements Comparable<Pairs>
    {
        int value,index;
        Pairs(int value, int index)
        {
            this.value = value;
            this.index = index;
        }
        public int compareTo(Pairs p)
        {
            return Integer.compare(this.value,p.value);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pairs)) return false;
            Pairs pairs = (Pairs) o;
            return value == pairs.value && index == pairs.index;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value, index);
        }
    }
}
class FastScanner
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer str = new StringTokenizer("");

    String next() throws IOException
    {
        while(!str.hasMoreTokens())
            str = new StringTokenizer(br.readLine());

        return str.nextToken();
    }

    char nextChar() throws IOException {
        return next().charAt(0);
    }

    int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }

    float nextfloat() throws IOException
    {
        return Float.parseFloat(next());
    }

    double nextDouble() throws IOException
    {
        return Double.parseDouble(next());
    }
    long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }
    byte nextByte() throws IOException
    {
        return Byte.parseByte(next());
    }
    int [] arrayIn(int n) throws IOException
    {
        int[] arr = new int[n];
        for(int i=0; i<n; i++)
        {
            arr[i] = nextInt();
        }
        return arr;
    }
}

