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.util.*;
import java.io.*;
import java.math.*;

public class Main

{ 
	 static FastReader sc=new FastReader(); 
	 static long dp[][][];
	 static int mod=1000000007;
	 
	  public static void main(String[] args)  throws IOException
{
		    //CHECK FOR N=1
       	//CHECK FOR N=1
	    //CHECK FOR N=1			
       	//CHECK FOR N=1
		  
		  
		  
		   PrintWriter out=new PrintWriter(System.out);
		   StringBuffer sb=new StringBuffer("");
		  int ttt=1;
		// ttt =i(); 	
		   
	        outer :while (ttt-- > 0) 
			{

	        	int n=i();
	        	String A[]=inputS(2*n-2);
	        	ArrayList<String> l=new ArrayList<String>();
	        	for(int i=0;i<A.length;i++) {
	        		if(A[i].length()==n-1) {
	        			l.add(A[i]);
	        		}
	        	}
	        	HashMap<String,Integer> map=new HashMap<String, Integer>();
	        	for(String s : A) {
	        		if(map.containsKey(s)) {
	        			map.put(s, map.get(s)+1);
	        		}
	        		else
	        			map.put(s, 1);
	        	}
	        	
	        	
	        	String a=l.get(0);
	        	String b=l.get(1);
	        	boolean ans=true;
	        	for(int i=n-1;i>0;i--) {
	        		String s=a.substring(0,i);
	        		if(!map.containsKey(s)) {
	        			ans=false;
	        			break;
	        		}
	        		map.put(s, map.get(s)-1);
	        		if(map.get(s)==0)
	        			map.remove(s);
	        	}
	        	for(int i=0;i<n-1;i++) {
	        		String s=b.substring(i,n-1);
	        		if(!map.containsKey(s)) {
	        			
	        			ans=false;
	        			break;
	        		}
	        		map.put(s, map.get(s)-1);
	        		if(map.get(s)==0)
	        			map.remove(s);
	        	}
	        	int R[]=new int[n*2-2];
	        	if(ans) {
	        		for(int i=n-1;i>0;i--) {
		        		String s=a.substring(0,i);
		        		for(int j=0;j<A.length;j++) {
		        			if(R[j]!=0)
		        				continue;
		        			if(A[j].equals(s)) {
		        				R[j]=1;
		        				break;
		        			}
		        		}
	        		}
	        		for(int i=0;i<n-1;i++) {
		        		String s=b.substring(i,n-1);
		        		for(int j=0;j<A.length;j++) {
		        			if(R[j]!=0)
		        				continue;
		        			if(A[j].equals(s)) {
		        				R[j]=2;
		        				break;
		        			}
		        		}
	        		}
	        	}
	        	else {
	        		map.clear();
	        		for(String s : A) {
		        		if(map.containsKey(s)) {
		        			map.put(s, map.get(s)+1);
		        		}
		        		else
		        			map.put(s, 1);
		        	}
		        	 a=l.get(1);
		        	 b=l.get(0);
		        	 ans=true;
		        	for(int i=n-1;i>0;i--) {
		        		String s=a.substring(0,i);
		        		if(!map.containsKey(s)) {
		        			ans=false;
		        			break;
		        		}
		        		map.put(s, map.get(s)-1);
		        		if(map.get(s)==0)
		        			map.remove(s);
		        	}
		        	for(int i=0;i<n-1;i++) {
		        		String s=b.substring(i,n-1);
		        		if(!map.containsKey(s)) {
		        			ans=false;
		        			break;
		        		}
		        		map.put(s, map.get(s)-1);
		        		if(map.get(s)==0)
		        			map.remove(s);
		        	}
		        	for(int i=n-1;i>0;i--) {
		        		String s=a.substring(0,i);
		        		for(int j=0;j<A.length;j++) {
		        			if(R[j]!=0)
		        				continue;
		        			if(A[j].equals(s)) {
		        				R[j]=1;
		        				break;
		        			}
		        		}
	        		}
	        		for(int i=0;i<n-1;i++) {
		        		String s=b.substring(i,n-1);
		        		for(int j=0;j<A.length;j++) {
		        			if(R[j]!=0)
		        				continue;
		        			if(A[j].equals(s)) {
		        				R[j]=2;
		        				break;
		        			}
		        		}
	        		}
	        		
	        	}
	        	for(int i=0;i<R.length;i++) {
	        		if(R[i]==1) {
	        			System.out.print("P");
	        		}
	        		else
	        			System.out.print("S");
	        	}
	        	
	        	
	        	
			}
		     out.close();
    	//System.out.println(sb.toString());
	     
	     
	    //CHECK FOR N=1                    //CHECK FOR M=0
        //CHECK FOR N=1                    //CHECK FOR M=0
       	//CHECK FOR N=1
       	//CHECK FOR N=1
       	//CHECK FOR N=1
		        
		     
    }
		


static int[] input(int n) {
	int A[]=new int[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.nextInt();
	   }
	   return A;
   }
static long[] inputL(int n) {
	long A[]=new long[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.nextLong();
	   }
	   return A;
   }
static String[] inputS(int n) {
	String A[]=new String[n];
	   for(int i=0;i<n;i++) {
		   A[i]=sc.next();
	   }
	   return A;
   }
static long sum(int A[]) {
	long sum=0;
	for(int i : A) {
		sum+=i;
	}
	return sum;
}
static long sum(long A[]) {
	long sum=0;
	for(long i : A) {
		sum+=i;
	}
	return sum;
}
static void reverse(long A[]) {
	int n=A.length;
	long B[]=new long[n];
	for(int i=0;i<n;i++) {
		B[i]=A[n-i-1];
	}
	for(int i=0;i<n;i++)
		A[i]=B[i];
	
}
static void reverse(int A[]) {
	int n=A.length;
	int B[]=new int[n];
	for(int i=0;i<n;i++) {
		B[i]=A[n-i-1];
	}
	for(int i=0;i<n;i++)
		A[i]=B[i];
	
}
static void input(int A[],int B[]) {
	   for(int i=0;i<A.length;i++) {
		   A[i]=sc.nextInt();
		   B[i]=sc.nextInt();
	   }
}
static int[][] input(int n,int m){
	int A[][]=new int[n][m];
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			A[i][j]=i();
		}
	}
	return A;
}
static char[][] charinput(int n,int m){
	char A[][]=new char[n][m];
	for(int i=0;i<n;i++) {
		String s=s();
		for(int j=0;j<m;j++) {
			A[i][j]=s.charAt(j);
		}
	}
	return A;
}
static int max(int A[]) {
	int max=Integer.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static int min(int A[]) {
	int min=Integer.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long max(long A[]) {
	long max=Long.MIN_VALUE;
	for(int i=0;i<A.length;i++) {
		max=Math.max(max, A[i]);
	}
	return max;
}
static long min(long A[]) {
	long min=Long.MAX_VALUE;
	for(int i=0;i<A.length;i++) {
		min=Math.min(min, A[i]);
	}
	return min;
}
static long [] prefix(long A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] prefix(int A[]) {
	long p[]=new long[A.length];
	p[0]=A[0];
	for(int i=1;i<A.length;i++)
		p[i]=p[i-1]+A[i];
	return p;
}
static long [] suffix(long A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static long [] suffix(int A[]) {
	long p[]=new long[A.length];
	p[A.length-1]=A[A.length-1];
	for(int i=A.length-2;i>=0;i--)
		p[i]=p[i+1]+A[i];
	return p;
}
static void print(int A[]) {
	for(int i : A) {
		System.out.print(i+" ");
	}
	System.out.println();
}
static void print(long A[]) {
	for(long i : A) {
		System.out.print(i+" ");
	}
	System.out.println();
}
static long mod(long x) {
	 int mod=1000000007;
	  return ((x%mod + mod)%mod);
}
static String reverse(String s) {
	StringBuffer p=new StringBuffer(s);
	p.reverse();
	return p.toString();
}

     static int i() {
    	 return sc.nextInt();
     }
     static String s() {
    	 return sc.next();
     }
     static long l() {
    	 return sc.nextLong();
     }  
     static void sort(int[] A){
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
     }
     static void sort(long[] A){
	        int n = A.length;
	        Random rnd = new Random();
	        for(int i=0; i<n; ++i){
	            long tmp = A[i];
	            int randomPos = i + rnd.nextInt(n-i);
	            A[i] = A[randomPos];
	            A[randomPos] = tmp;
	        }
	        Arrays.sort(A);
	     }
  static String sort(String s) {
 	 Character ch[]=new Character[s.length()];
 	 for(int i=0;i<s.length();i++) {
 		 ch[i]=s.charAt(i);
 	 }
 	 Arrays.sort(ch);
 	 StringBuffer st=new StringBuffer("");
 	 for(int i=0;i<s.length();i++) {
 		 st.append(ch[i]);
 	 }
 	 return st.toString();
  }
  static HashMap<Integer,Integer> hash(int A[]){
	  HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
	  for(int i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
  }
  static TreeMap<Integer,Integer> tree(int A[]){
	  TreeMap<Integer,Integer> map=new TreeMap<Integer, Integer>();
	  for(int i : A) {
		  if(map.containsKey(i)) {
			  map.put(i, map.get(i)+1);
		  }
		  else {
			  map.put(i, 1);
		  }
	  }
	  return map;
  }
     static boolean prime(int n) 
	    { 
	        if (n <= 1) 
	            return false; 
	        if (n <= 3) 
	            return true; 
	        if (n % 2 == 0 || n % 3 == 0) 
	            return false; 
	        double sq=Math.sqrt(n);
	  
	        for (int i = 5; i <= sq; i = i + 6) 
	            if (n % i == 0 || n % (i + 2) == 0) 
	                return false; 
	        return true; 
	    } 
     static boolean prime(long n) 
	    { 
	        if (n <= 1) 
	            return false; 
	        if (n <= 3) 
	            return true; 
	        if (n % 2 == 0 || n % 3 == 0) 
	            return false; 
	        double sq=Math.sqrt(n);
	  
	        for (int i = 5; i <= sq; i = i + 6) 
	            if (n % i == 0 || n % (i + 2) == 0) 
	                return false; 
	        return true; 
	    } 
     static int gcd(int a, int b) 
     { 
         if (a == 0) 
             return b; 
         return gcd(b % a, a); 
     } 
     static long gcd(long a, long b) 
     { 
         if (a == 0) 
             return b; 
         return gcd(b % a, a); 
     } 
     static class Pair implements Comparable<Pair>
     {
    	 int x;
    	 int y;
    	 int z;
    	 Pair(int x,int y,int z){
    		 this.x=x;
    		 this.y=y;
    		 this.z=z;
    	 }
		@Override
//		public int compareTo(Pair o) {
//			if(this.x>o.x)
//				return 1;
//			else if(this.x<o.x)
//				return -1;
//			else {
//				if(this.y>o.y)
//					return 1;
//				else if(this.y<o.y)
//					return -1;
//				else
//					return 0;
//			}
//		}
		public int compareTo(Pair o) {
			if(this.x>o.x)
				return 1;
			else if(this.x<o.x)
				return -1;
			else {
				
					return 0;
			}
		}
		
		
     }
        
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            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; 
        } 
    } 
} 



