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.*;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.net.ssl.SSLContext;

public class Main
{  
   static long mod=(long)998244353;
   static long inf=1000000007;
   static int[] sieve;
   static ArrayList<Integer> primes;

   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     fast s = new fast();
	     PrintWriter out=new PrintWriter(System.out);
	     Scanner sc=new Scanner(System.in);
	     StringBuilder fans = new StringBuilder();
	     
         int n=s.nextInt();
         
         String ans1=new String();
         String ans2=new String();
         int max=-1;
         String str2=new String();
         
         String str_arr[]=new String[2*n+3];
         
         for(int i=1;i<=(2*n-2);i++)
        	 {
        		 String str=s.nextLine();
        		 str_arr[i]=new String(str);
        		 if(str.length()>max) 
        			 {
        				 max=str.length();
        				 ans1=new String(str);
        			 }
        	 }
         
         for(int i=1;i<=(2*n-2);i++)
        	 {
        		 if(str_arr[i].length()==max) 
        			 {
        				 str2=new String(str_arr[i]);
        			 }
        	 }

         ans2=str2.concat(Character.toString(ans1.charAt(ans1.length()-1)));
         ans1=ans1.concat(Character.toString(str2.charAt(str2.length()-1)));
        
         
         HashSet<String> hm=new HashSet<String>();

         int org_length=ans1.length();
		
         int second=0;
         
         for(int i=1;i<=(2*n-2);i++)
        	 {
        		 int len=str_arr[i].length();
        		 
        		 int flag1=0; int flag2=0;
        		 
        		 int count=0;
        		 for(int j=0;j<len;j++)
        			 {
        			 if(str_arr[i].charAt(j)==ans1.charAt(j)) count++;
        			 else break;
        			 }
        		 if(count==len) flag1=1;

        		 count=0;
        		 for(int j=0;j<len;j++)
        			 {
        			 if(str_arr[i].charAt(len-j-1)==ans1.charAt(org_length-j-1)) count++;
        			 else break;
        			 }
        		 if(count==len) flag2=1;
        		
        		 if(flag1==1 && flag2==1)
        			 {
        				 if(!hm.contains(str_arr[i]))
        					 {
        						 fans.append("P");
        						 hm.add(str_arr[i]);
        					 }
        				 else
        					 fans.append("S");
        			 }
        		 else if(flag1==1) fans.append("P");
        		 else if(flag2==1) fans.append("S");
        		 
        		 if(flag1==0 && flag2==0)
        			 {
        				 second=1;
        				 break;
        			 }
        	 }
         
             if(second==0) System.out.println(fans);
             else
            	 {
            		 org_length=ans2.length();
            		 hm=new HashSet<String>();
            		
            		 fans=new StringBuilder("");
            		 for(int i=1;i<=(2*n-2);i++)
                    	 {
                    		 int len=str_arr[i].length();
                    		 
                    		 int flag1=0; int flag2=0;
                    		 
                    		 int count=0;
                    		 for(int j=0;j<len;j++)
                    			 {
                    			 if(str_arr[i].charAt(j)==ans2.charAt(j)) count++;
                    			 else break;
                    			 }
                    		 if(count==len) flag1=1;

                    		 count=0;
                    		 for(int j=0;j<len;j++)
                    			 {
                    			 if(str_arr[i].charAt(len-j-1)==ans2.charAt(org_length-j-1)) count++;
                    			 else break;
                    			 }
                    		 if(count==len) flag2=1;
                    		
                    		 if(flag1==1 && flag2==1)
                    			 {
                    				 if(!hm.contains(str_arr[i]))
                    					 {
                    						 fans.append("P");
                    						 hm.add(str_arr[i]);
                    					 }
                    				 else
                    					 fans.append("S");
                    			 }
                    		 else if(flag1==1) fans.append("P");
                    		 else if(flag2==1) fans.append("S");
                    		 
                    		 if(flag1==0 && flag2==0)
                    			 {
                    				 second=1;
                    				 break;
                    			 }
                    	 }
            		 System.out.println(fans);
            	 }
     }




static class fast {   
		private InputStream i;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;

			  
			   for(j=i+1;j<n && a[i]<a[j];j++);

			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		   
		public static void division(char ch[],int divisor)
		   {
			   int div=Character.getNumericValue(ch[0]); int mul=10;int remainder=0;
			   StringBuilder quotient=new StringBuilder("");
			   for(int i=1;i<ch.length;i++)
			   {
				   div=div*mul+Character.getNumericValue(ch[i]);	
				   if(div<divisor) {quotient.append("0");continue;}
				   quotient.append(div/divisor);
				   div=div%divisor;mul=10;
				   
			   } 
			   remainder=div;
			   while(quotient.charAt(0)=='0')quotient.deleteCharAt(0);	   
			   System.out.println(quotient+" "+remainder);	  
		   }
		
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			primes=new ArrayList<Integer>();
			sieve[1]=1;
			for(int i=2;i<=Math.sqrt(size);i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) sieve[j]=1;
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long n, long b, long MOD)
		   {
		       long x=1;long y=n; 
		       while(b > 0)
		       {
		           if(b%2 == 1)
		           {
		               x=x*y;
		               if(x>MOD) x=x%(MOD);
		           }
		           y = y*y;
		           if(y>MOD) y=y%(MOD); 
		           b >>= 1;
		       }
		       return x;
		   }


		public static long mod_inv(long n,long mod)
		{
			return pow(n,mod-2,mod);
		}
		
		 public static int upper(Integer[] a,int start,int end,int key)
		 {
			   int mid=(start+end)>>1;
			   if(start==end && a[mid]<key) {return -1;}
			   if(start>end) return -1;

			   if(a[mid]>=key && (((mid-1)>=0 && a[mid-1]<key) || (mid-1)==0)) return mid;
			   else if(a[mid]== key && (mid-1)>=0 && a[mid-1]==key) return lower(a,start,mid-1,key);   
			   else if(key>a[mid]) return lower(a,mid+1,end,key);
			   else return lower(a,start,mid-1,key);
		}
		 
		 public static int lower(Integer a[],int start,int end,int key)
		 {
			   int mid=(start+end)>>1;
			   if(start==end && a[mid]>key) {return -1;}
			   if(start>end) return -1;

			   if(a[mid]<=key && (((mid+1)<a.length && a[mid+1]>key) || (mid+1)==a.length)) return mid;
			   else if(a[mid]== key && (mid+1)<a.length && a[mid+1]==key) return upper(a,mid+1,end,key);   
			   else if(key>=a[mid]) return upper(a,mid+1,end,key);
			   else return upper(a,start,mid-1,key);
		} 
		   
		public int gcd(int a,int b)
		{
			if(a==0) return b;
			return gcd(b%a,a);
		}
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}	
}