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.OutputStreamWriter;
import java.io.PrintWriter;

import java.util.*;

public class A_GENERAL {
   
	// for fast output printing  : use printwriter or stringbuilder
	// remember to close pw using pw.close()
	static StringBuilder sb = new StringBuilder();
	static long seive_size = (long) 1e6;
	static String alpha = "abcdefghijklmnopqrstuvwxyz";
    static ArrayList<Integer> primes = new ArrayList<>();
    static boolean[] set = new boolean[(int) seive_size+1];
    static int n, m;
    static ArrayList<Integer>[] adj;
    static boolean[] visited;
    static ArrayDeque<Integer> q = new ArrayDeque<>();
    static final long MOD = 998244353;
    static long[][] arr;
    static int[] dist;
    
	public static void main(String[] args) {
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		MyScanner sc = new MyScanner();
		n = sc.nextInt();
		
		String[] p = new String[n];
		String[] s = new String[n];
		P[] plist = new P[2*n-2];
		for(int i = 0; i < 2*n-2; i++) {
			plist[i] = new P(sc.next(), i);
		}
		Arrays.sort(plist);
		String prev = plist[0].s;
		String next = plist[1].s;

		char[] ans = new char[2*n-2];
		if(prev.equals(next)) {
			p[0] = prev;
			s[0] = next;
			ans[plist[0].k] = 'P';
			ans[plist[1].k] = 'S';
		} else if(n > 2) {
			if((plist[3].s.startsWith(plist[0].s) && plist[2].s.endsWith(plist[1].s)) 
					|| (plist[2].s.startsWith(plist[0].s) && plist[3].s.endsWith(plist[1].s))) {
				prev = plist[0].s;
				next = plist[1].s;
				ans[plist[0].k] = 'P';
				ans[plist[1].k] = 'S';
			} else {
				prev = plist[1].s;
				next = plist[0].s;
				ans[plist[0].k] = 'S';
				ans[plist[1].k] = 'P';
			}
		}
		if(n == 2) {
			ans[plist[0].k] = 'P';
			ans[plist[1].k] = 'S';
		}
		for(int i = 2; i < plist.length; i+=2) {
			String a = plist[i].s;
			String b = plist[i+1].s;
			if(a.equals(b)) {
				p[i/2] = a;
				s[i/2] = b;
				ans[plist[i].k] = 'P';
				ans[plist[i+1].k] = 'S';
				prev = a;
				next = b;
				continue;
			}
			if(a.startsWith(prev) && b.endsWith(next)) {
				prev = a;
				next = b;
				ans[plist[i].k] = 'P';
				ans[plist[i+1].k] = 'S';
			} else {
				prev = b; 
				next = a;
				ans[plist[i].k] = 'S';
				ans[plist[i+1].k] = 'P';
			}
		}
		for(int i = 0; i < 2*n-2; i++) {
			System.out.print(ans[i]);
		}
		out.close();
	}
	
	public static void dfs(int u) {
		visited[u] = true;
		for(int v : adj[u]) {
			if(!visited[v]) {
				dfs(v);
			}
		}
	}

	public static class P implements Comparable<P>{
		String s;
		int k;
		P(String s, int k) {
			this.s = s;
			this.k = k;
		}
		@Override
		public int compareTo(P o) {
			return Integer.compare(this.s.length(), o.s.length());
		}
		
	}
	
	public static class Pair {
		long f;
		long s;
		Pair(long f, long s) {
			this.f = f;
			this.s = s;
		}
	}
	public static void init(int n) {
    	adj = new ArrayList[n+1];
    	visited = new boolean[n+1];
    	for(int i = 1; i <= n; i++)
			adj[i] = new ArrayList();
    }
	// print string "s" multiple times 
	// prefer to use this function for multiple printing
	public static String mp(String s, int times) {
		return String.valueOf(new char[times]).replace("\0", s);
	}
	// take log with base 2
 	public static long log2(long k) {
 		return 63-Long.numberOfLeadingZeros(k);
 	}

 	// using lambda function for sorting
   	public static void lambdaSort() {
   		Arrays.sort(arr, (a, b) -> Double.compare(a[0], b[0]));
   	}
  	
  	// (n choose k) = (n/k) * ((n-1) choose (k-1))
  	public static long choose(long n, long k) {
 		return (k == 0) ? 1 : (n*choose(n-1, k-1))/k;
 	}

 	// just for keeping gcd function for other personal purposes
 	public static long gcd(long a, long b) {
 		return (a == 0) ? b : gcd(b%a, a);
 	}
 	
	public static long max(long... as) {
        long max = Long.MIN_VALUE;
        for (long a : as) max = Math.max(a, max);
        return max;
    }

    public static long min(int... as) {
        long min = Long.MAX_VALUE;
        for (long a : as) min = Math.min(a, min);
        return min;
    }
 	
    public static long modpow(long x, long n, long mod) {
    	if(n == 0) return 1%mod;
    	long u = modpow(x, n/2, mod);
    	u = (u*u)%mod;
    	if(n%2 == 1) u = (u*x)%mod;
    	return u;
    }
 	// ======================= binary search (lower and upper bound) =======================
	public static int lowerBound(long[] a, int x) {
		int lo = 0;
 		int hi = a.length-1;
 		int ans = -1;
 		while(lo <= hi) {
 			int mid = (lo+hi)/2;
 			if(x < a[mid]) {
 				hi = mid-1;
 			} else if(x > a[mid]) {
 				lo = mid+1;
 			} else if(lo != hi) {
 				 hi = mid-1; 		// for first occurrence
 				 ans = mid;
 			} else {
 				return mid;
 			}
 		}
 		return ans;
	}
	
	public static int upperBound(long[] a, long x) {
		int lo = 0;
		int hi = a.length-1;
		int ans = -1;
		while(lo <= hi) {
			int mid = (lo+hi)/2;
			if(x < a[mid]) {
				hi = mid-1;
			} else if(x > a[mid]) {
				lo = mid+1;
			} else if(lo != hi) {
				lo = mid+1;			// for last occurrence
				ans = mid;
			} else {
				return mid;
			}
		}
		return ans;
	}
	// ================================================================

	// ================== SEIVE OF ERATOSTHENES =======================
	// Complexity : O(N * log(log(N)))       ( almost O(N) )
	public static void generatePrimes() {
		// set.add(0);
		// set.add(1);
		Arrays.fill(set, true);
		set[0] = false;
		set[1] = false;
		for(int i = 2; i <= seive_size; i++) {
			if(set[i]) {
				for(long j = (long) i*i; j <= seive_size; j+=i) 
					set[(int)j] = false;
				primes.add(i);
			}
		}
	}
  
	public static boolean isPrime(long N) {
		if(N <= seive_size) return set[(int)N];
		for (int i = 0; i < (int)primes.size(); i++)
			if (N % primes.get(i) == 0) return false;
		return true;
	}
	// ===========================================================
  
 	// ================ Permutation of String ====================
 	public static void permute(String str) {
 		permute(str, 0, str.length()-1);
 	}
 	public static void permute(String str, int l, int r) 
    { 
        if (l == r) 
            System.out.println(str); 
        else
        { 
            for (int i = l; i <= r; i++) 
            { 
                str = swap(str,l,i); 
                permute(str, l+1, r); 
                str = swap(str,l,i); 
            } 
        } 
    }
	public static String swap(String a, int i, int j) 
    { 
        char temp; 
        char[] charArray = a.toCharArray(); 
        temp = charArray[i] ; 
        charArray[i] = charArray[j]; 
        charArray[j] = temp; 
        return String.valueOf(charArray); 
    } 
	// Union-find
	void makeSet(int parent[], int rank[]) {

		int i;
		for(i = 0; i < parent.length; i++) {
			parent[i] = i;
			rank[i] = 0;
		}
	}
	public static int find(int u, int parent[]) {

		if(parent[u] == u)	return u;

		int v = find(parent[u], parent);
		parent[u] = v;
		return v;

	}
	public static boolean connected(int u, int v, int[] parent) {
		return find(u, parent) == find(v, parent);
	}
	public static void Union(int u, int v, int rank[], int parent[]) {

		int x = find(u, parent);				//root of u
		int y = find(v, parent);				//root of v

		if(x == y)		return;
		if(rank[x] == rank[y]) {
			parent[y] = x;
			rank[x]++;
		}
		else if(rank[x] > rank[y]) {
			parent[y] = x;
		}
		else {
			parent[x] = y;
		}

	}
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
		int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
	}

}