There are N players standing in a line, indexed 1 to N from left to right. They all play a game of Rock, Paper, Scissors. Each player has already decided which move they want to play. You are given this information as a string S of length N, i.e,

S_{i} is equal to \verb+R+ if player i will play Rock.
S_{i} is equal to \verb+P+ if player i will play Paper.
S_{i} is equal to \verb+S+ if player i will play Scissors.

Let W(i, j) denote the move played by the winner if players i, i+1, \ldots, j compete in order from left to right. That is, 
First, players i and i+1 play a game
The winner of this game plays against player i+2
The winner of the second game plays against player i+3

\vdots

The winner of the first j-i-1 games plays against player j, and the move played by the winner of this game is declared to be W(i, j).

If i = j, then player i is considered to be the winner and W(i, i) = S_{i}.

Your task is to find the value of W(i,N) for all i from 1 to N.

Note : 
If a person with index i and index j (i < j) play against each other, then:
If S_{i} \neq S_{j}, the winner is decided by classical rules, i.e, rock beats scissors, scissors beats paper, and paper beats rock.
If S_{i} = S_{j}, the player with lower index (in this case, i) wins.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N, the number of players.
- The second line of each test case contains the string S of length N, denoting the moves chosen by the players.

------ Output Format ------ 

For each test case, print a single line containing a string of length N, whose i-th character is W(i, N).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 5\cdot 10^{5}$
$S_{i}$ is either $\verb+R+$, $\verb+P+$ or $\verb+S+$
- Sum of $N$ over all test cases doesn't exceed $5 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (10 points):
$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5000$
Sum of $N$ over all test cases doesn't exceed $5000$

Subtask 2 (90 points):
Original constraints

----- Sample Input 1 ------ 
2
1
S
4
SSPR
----- Sample Output 1 ------ 
S
RRPR
----- explanation 1 ------ 

Test Case 1. $W(1,1) = \verb+S+$ as there is only one player.   

Test Case 2.

For $W(1,4)$ the game is played as follows  :
- Player $1$ and $2$ compete, player $1$ wins.
- Player $1$ and $3$ compete, player $1$ wins.
- Player $1$ and $4$ compete, player $4$ wins.

Hence, we print $W(1,4) = S_{4} = \verb+R+$

For $W(3,4)$ the game is played as follows  :
- Player $3$ and $4$ compete, player $3$ wins.

Hence, we print $W(3,4) = S_{3} = \verb+P+$

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Sorting

Data structures


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	result = [''] * n
	map_s = {'R': 'P', 'P': 'S', 'S': 'R'}
	map_ind = {}
	for i in range(n - 1, -1, -1):
		t = map_s[s[i]]
		if t in map_ind:
			result[i] = result[map_ind[t]]
		else:
			result[i] = s[i]
		map_ind[s[i]] = i
	print(''.join((_ for _ in result)))


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	result = []
	result.append(s[-1])
	dp = {}
	dp[s[-1]] = s[-1]
	for i in range(n - 1, 0, -1):
		if s[i - 1] == 'P' and 'S' in dp:
			result.append(dp['S'])
			dp['P'] = dp['S']
		elif s[i - 1] == 'S' and 'R' in dp:
			result.append(dp['R'])
			dp['S'] = dp['R']
		elif s[i - 1] == 'R' and 'P' in dp:
			result.append(dp['P'])
			dp['R'] = dp['P']
		else:
			result.append(s[i - 1])
			dp[s[i - 1]] = s[i - 1]
	result.reverse()
	print(''.join((_ for _ in result)))


def A(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'
	else:
		return 'R'
t = int(input())
for i in range(t):
	n = int(input())
	ans = [0] * n
	a = input()
	if n == 1:
		print(a[0])
	else:
		r = [0] * n
		p = [0] * n
		s = [0] * n
		ch = ''
		ans[n - 1] = a[n - 1]
		r[n - 2] = A('R', a[n - 1])
		p[n - 2] = A('P', a[n - 1])
		s[n - 2] = A('S', a[n - 1])
		if a[n - 2] == 'R':
			ans[n - 2] = r[n - 2]
		elif a[n - 2] == 'P':
			ans[n - 2] = p[n - 2]
		elif a[n - 2] == 'S':
			ans[n - 2] = s[n - 2]
		for i in range(n - 3, -1, -1):
			temp = A('R', a[i + 1])
			if temp == 'R':
				r[i] = r[i + 1]
			elif temp == 'P':
				r[i] = p[i + 1]
			else:
				r[i] = s[i + 1]
			temp = A('P', a[i + 1])
			if temp == 'R':
				p[i] = r[i + 1]
			elif temp == 'P':
				p[i] = p[i + 1]
			else:
				p[i] = s[i + 1]
			temp = A('S', a[i + 1])
			if temp == 'R':
				s[i] = r[i + 1]
			elif temp == 'P':
				s[i] = p[i + 1]
			else:
				s[i] = s[i + 1]
			if a[i] == 'R':
				ans[i] = r[i]
			elif a[i] == 'P':
				ans[i] = p[i]
			else:
				ans[i] = s[i]
		print(''.join(ans))


def whowon(s1, s2):
	if s1 == 'P' and s2 == 'R':
		return s1
	elif s1 == 'P' and s2 == 'S':
		return s2
	elif s1 == 'P' and s2 == 'P':
		return s1
	elif s1 == 'R' and s2 == 'S':
		return s1
	elif s1 == 'R' and s2 == 'P':
		return s2
	elif s1 == 'R' and s2 == 'R':
		return s1
	elif s1 == 'S' and s2 == 'S':
		return s1
	elif s1 == 'S' and s2 == 'P':
		return s1
	elif s1 == 'S' and s2 == 'R':
		return s2

def getarrayrow(x):
	if x == 'S':
		return 0
	if x == 'R':
		return 1
	if x == 'P':
		return 2
T = int(input())
for _ in range(T):
	answer = ''
	size = int(input())
	data = input()
	data = list(data)
	arr = [[0 for i in range(size)] for j in range(3)]
	for i in range(size - 2, -1, -1):
		j = i
		x = data[j]
		while j != size - 1:
			if arr[getarrayrow(x)][j + 1] == 0:
				x = whowon(x, data[j + 1])
				j += 1
			else:
				x = arr[getarrayrow(x)][j + 1]
				break
		arr[getarrayrow(data[i])][i + 1] = x
	for i in range(size - 1):
		answer += str(arr[getarrayrow(data[i])][i + 1])
	answer += data[size - 1]
	print(answer)


t = int(input())
for i in range(t):
	d1 = dict(R='P', S='R', P='S')
	d2 = dict(R=-1, S=-1, P=-1)
	n = int(input())
	s = list(input())
	ans = [0] * n
	for j in range(n - 1, -1, -1):
		c = d2[d1[s[j]]]
		if c == -1:
			ans[j] = s[j]
		else:
			ans[j] = ans[c]
		d2[s[j]] = j
	print(''.join(ans))


for _ in range(int(input())):
	d = dict(R='P', S='R', P='S')
	d1 = dict(R=-1, S=-1, P=-1)
	n = int(input())
	game = list(input())
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		idx = d1[d[game[i]]]
		if idx == -1:
			ans[i] = game[i]
		else:
			ans[i] = ans[idx]
		d1[game[i]] = i
	print(''.join(ans))


def battle(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'
	else:
		return 'R'
t = int(input())
for i in range(t):
	N = int(input())
	result = [0] * N
	a = input()
	if N == 1:
		print(a[0])
	else:
		R = [0] * N
		P = [0] * N
		S = [0] * N
		ch = ''
		result[N - 1] = a[N - 1]
		R[N - 2] = battle('R', a[N - 1])
		P[N - 2] = battle('P', a[N - 1])
		S[N - 2] = battle('S', a[N - 1])
		if a[N - 2] == 'R':
			result[N - 2] = R[N - 2]
		elif a[N - 2] == 'P':
			result[N - 2] = P[N - 2]
		elif a[N - 2] == 'S':
			result[N - 2] = S[N - 2]
		for i in range(N - 3, -1, -1):
			temp = battle('R', a[i + 1])
			if temp == 'R':
				R[i] = R[i + 1]
			elif temp == 'P':
				R[i] = P[i + 1]
			else:
				R[i] = S[i + 1]
			temp = battle('P', a[i + 1])
			if temp == 'R':
				P[i] = R[i + 1]
			elif temp == 'P':
				P[i] = P[i + 1]
			else:
				P[i] = S[i + 1]
			temp = battle('S', a[i + 1])
			if temp == 'R':
				S[i] = R[i + 1]
			elif temp == 'P':
				S[i] = P[i + 1]
			else:
				S[i] = S[i + 1]
			if a[i] == 'R':
				result[i] = R[i]
			elif a[i] == 'P':
				result[i] = P[i]
			else:
				result[i] = S[i]
		print(''.join(result))


import sys
input = sys.stdin.readline
T = int(input())

def find_winner(a, b):
	if a == 'R' and b == 'S':
		return a
	elif a == 'S' and b == 'P':
		return a
	elif a == 'P' and b == 'R':
		return a
	else:
		return b

def is_a_winner(a, b):
	if a == 'R' and b == 'S':
		return True
	elif a == 'S' and b == 'P':
		return True
	elif a == 'P' and b == 'R':
		return True
	else:
		return False

def is_won(p1, p2):
	result = False
	if p1 == 'R':
		return p2 == 'S'
	elif p1 == 'P':
		return p2 == 'R'
	else:
		return p2 == 'P'

def find_ans(m, n):
	global N, S
	winner_char = find_winner(m, S[n + 10])
	if n == N - 1:
		return winner_char
	else:
		return find_ans(winner_char, n + 1)

def testcase():

	def roll_win(i, j):
		result = S[i - 1]
		while j < N and is_won(S[i - 1], S[j]):
			j += 1
		if j < N:
			result = answer[j]
		return result
	N = int(input())
	S = input()
	answer = [''] * N
	answer[N - 1] = S[N - 1]
	for i in range(N - 1, 0, -1):
		if is_won(S[i - 1], S[i]):
			j = i + 1
			answer[i - 1] = roll_win(i, j)
		else:
			answer[i - 1] = answer[i]
	print(''.join(answer))
for _ in range(T):
	testcase()


import sys
input = sys.stdin.readline
T = int(input())

def find_winner(a, b):
	if a == 'R' and b == 'S':
		return a
	elif a == 'S' and b == 'P':
		return a
	elif a == 'P' and b == 'R':
		return a
	else:
		return b

def is_a_winner(a, b):
	if a == 'R' and b == 'S':
		return True
	elif a == 'S' and b == 'P':
		return True
	elif a == 'P' and b == 'R':
		return True
	else:
		return False

def find_ans(m, n):
	global N, S
	winner_char = find_winner(m, S[n + 10])
	if n == N - 1:
		return winner_char
	else:
		return find_ans(winner_char, n + 1)
for _ in range(T):
	N = int(input())
	S = input()
	answer = [''] * N
	answer[N - 1] = S[N - 1]
	for i in range(N - 1, 0, -1):
		if is_a_winner(S[i - 1], S[i]):
			j = i + 1
			ans = S[i - 1]
			while j < N:
				if is_a_winner(S[i - 1], S[j]):
					j += 1
				else:
					ans = answer[j]
					break
			answer[i - 1] = ans
		else:
			answer[i - 1] = answer[i]
	print(''.join(answer))


who_beats = {'R': 'P', 'P': 'S', 'S': 'R'}
for _ in range(int(input())):
	n = int(input())
	s = input()
	ind = {'R': -1, 'P': -1, 'S': -1}
	ans = ['?'] * n
	for i in reversed(range(n)):
		indwb = ind[who_beats[s[i]]]
		ans[i] = s[i] if indwb == -1 else ans[indwb]
		ind[s[i]] = i
	print(''.join(ans))


try:

	def defence_win(a, b):
		win = [('R', 'P'), ('P', 'R'), ('R', 'S'), ('S', 'R'), ('S', 'P'), ('P', 'S')]
		it = win.index((a, b))
		w = ['P', 'P', 'R', 'R', 'S', 'S']
		return w[it]
	for _ in range(int(input())):
		lat_ner_rr = int(input())
		S = input()
		resultant_pro = [0] * lat_ner_rr
		i = 0
		if lat_ner_rr == 1:
			resultant_pro = [S]
		else:
			while i < lat_ner_rr:
				calcacher = [i]
				if resultant_pro[i] == 0:
					a = S[i]
					j = i + 1
					while j < lat_ner_rr:
						b = S[j]
						if a == b:
							resultant_noob = a
						else:
							resultant_noob = defence_win(a, b)
							a = resultant_noob
						if resultant_noob == b and resultant_pro[j] == 0:
							calcacher.append(j)
						elif resultant_noob == b and resultant_pro[j] != 0:
							resultant_noob = resultant_pro[j]
							j = lat_ner_rr
						j += 1
					if i == lat_ner_rr - 1:
						resultant_noob = a
					for items in calcacher:
						resultant_pro[items] = resultant_noob
				else:
					pass
				i += 1
		print(''.join(resultant_pro))
except:
	pass


try:

	def winner(a, b):
		win = [('R', 'P'), ('P', 'R'), ('R', 'S'), ('S', 'R'), ('S', 'P'), ('P', 'S')]
		it = win.index((a, b))
		w = ['P', 'P', 'R', 'R', 'S', 'S']
		return w[it]
	for _ in range(int(input())):
		N = int(input())
		S = input()
		ans = [0] * N
		i = 0
		if N == 1:
			ans = [S]
		else:
			while i < N:
				cache = [i]
				if ans[i] == 0:
					a = S[i]
					j = i + 1
					while j < N:
						b = S[j]
						if a == b:
							res = a
						else:
							res = winner(a, b)
							a = res
						if res == b and ans[j] == 0:
							cache.append(j)
						elif res == b and ans[j] != 0:
							res = ans[j]
							j = N
						j += 1
					if i == N - 1:
						res = a
					for items in cache:
						ans[items] = res
				else:
					pass
				i += 1
		print(''.join(ans))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	l = list((x for x in input()))
	w = [''] * len(l)
	d = {'R': -1, 'S': -1, 'P': -1}
	for i in range(len(l) - 1, -1, -1):
		if l[i] == 'S':
			if d['R'] == -1:
				w[i] = l[i]
			else:
				w[i] = w[d['R']]
			d['S'] = i
		elif l[i] == 'R':
			if d['P'] == -1:
				w[i] = l[i]
			else:
				w[i] = w[d['P']]
			d['R'] = i
		if l[i] == 'P':
			if d['S'] == -1:
				w[i] = l[i]
			else:
				w[i] = w[d['S']]
			d['P'] = i
	print(''.join(w))


import sys
inp_list = list(sys.stdin)
win_map = {'R': 'S', 'S': 'P', 'P': 'R'}
lose_map = {'S': 'R', 'R': 'P', 'P': 'S'}
all_vals_set = set(['R', 'S', 'P'])
for indx in range(1, len(inp_list)):
	if indx % 2 == 1:
		continue
	s = inp_list[indx].rstrip('\n')
	single_op_flag = False
	length = len(s)
	possible_outputs_set = set([s[-1], lose_map[s[-1]]])
	op = s[-1]
	switch_dict = {op: lose_map[op], lose_map[op]: op}
	for i in range(1, length):
		if s[length - i] == s[length - i - 1]:
			op += op[-1]
			continue
		if win_map[s[length - i - 1]] == s[length - i]:
			op += switch_dict[op[-1]]
		if lose_map[s[length - i - 1]] == s[length - i]:
			single_op_flag = True
			break
	if single_op_flag:
		op += op[-1] * (length - len(op))
	op = op[::-1]
	print(op)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	win_cycle = {'S': 'R', 'R': 'P', 'P': 'S'}
	indx = {'S': -1, 'R': -1, 'P': -1}
	ans = [''] * n
	for j in range(n - 1, -1, -1):
		ch = indx[win_cycle[s[j]]]
		if ch == -1:
			ans[j] = s[j]
		else:
			ans[j] = ans[ch]
		indx[s[j]] = j
	print(''.join(ans))


win = {'R': 'P', 'P': 'S', 'S': 'R'}
for i in range(int(input())):
	size = int(input())
	s = input()
	ans = ['?'] * size
	d = {'R': -1, 'P': -1, 'S': -1}
	for i in range(size - 1, -1, -1):
		x = d[win[s[i]]]
		if x == -1:
			ans[i] = s[i]
		else:
			ans[i] = ans[x]
		d[s[i]] = i
	for i in ans:
		print(i, end='')
	print()


def win(pl1, pl2):
	game = pl1 + pl2
	if game == 'SR' or game == 'RP' or game == 'PS':
		return False
	return True

def SPQR(S):
	if len(S) == 1:
		return S
	res = S[0]
	order = [(S[0], 0)]
	for i in range(1, len(S)):
		if win(order[0][0], S[i]):
			res = res + res[order[0][1]]
		elif len(order) == 1:
			res = res + S[i]
		else:
			res = res + res[order[1][1]]
		if S[i] != order[0][0]:
			order.insert(0, (S[i], i))
	return res[::-1]
T = int(input())
for t in range(T):
	N = int(input())
	print(SPQR(input()[::-1]))


def findans(s, n, overcome, idx):
	a = [-1 for k in range(n)]
	for j in range(n - 1, -1, -1):
		index = idx[overcome[s[j]]]
		if index == -1:
			a[j] = s[j]
		else:
			a[j] = a[index]
		idx[s[j]] = j
	return ''.join(a)
t = int(input())
overcome = {'R': 'P', 'P': 'S', 'S': 'R'}
for i in range(t):
	n = int(input())
	s = input()
	idx = {'R': -1, 'P': -1, 'S': -1}
	ans = findans(s, n, overcome, idx)
	print(ans)


test = int(input())
who_beat = {'R': 'P', 'P': 'S', 'S': 'R'}
for _ in range(test):
	n = int(input())
	s = input()
	ans = ['P'] * n
	idx = {'R': -1, 'S': -1, 'P': -1}
	for i in range(n - 1, -1, -1):
		competitor = who_beat[s[i]]
		cur = idx[competitor]
		if cur == -1:
			ans[i] = s[i]
		else:
			ans[i] = ans[cur]
		idx[s[i]] = i
	print(''.join(ans))


for _ in range(int(input())):
	n = int(input())
	A = input()
	d = {}
	d['R'] = 'P'
	d['P'] = 'S'
	d['S'] = 'R'
	ind = {}
	(ind['R'], ind['S'], ind['P']) = (-1, -1, -1)
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		idx = ind[d[A[i]]]
		if idx == -1:
			ans[i] = A[i]
		else:
			ans[i] = ans[idx]
		ind[A[i]] = i
	a = ''.join(ans)
	print(a)


win = {'R': 'P', 'P': 'S', 'S': 'R'}
for _ in range(int(input())):
	n = int(input())
	s = input()
	dic = {'S': -1, 'P': -1, 'R': -1}
	ans = ['?'] * n
	for i in reversed(range(n)):
		idx = dic[win[s[i]]]
		if idx == -1:
			ans[i] = s[i]
		else:
			ans[i] = ans[idx]
		dic[s[i]] = i
	print(''.join(ans))


def w(i):
	ind = s.find(comp[s[i]], i + 1)
	if ind == -1:
		d[f'w({i})'] = s[i]
		return s[i]
	else:
		d[f'w({i})'] = d[f'w({ind})']
		return d[f'w({ind})']
for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = ''
	d = {}
	comp = {'R': 'P', 'S': 'R', 'P': 'S'}
	for i in range(n - 1, -1, -1):
		ans += w(i)
	print(ans[::-1])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	dp = [0] * n
	dp[-1] = s[-1]
	idx = {'R': -1, 'P': -1, 'S': -1}
	idx[s[-1]] = n - 1
	if n > 1:
		wins = {'P': 'R', 'S': 'P', 'R': 'S'}
		loses = {'P': 'S', 'R': 'P', 'S': 'R'}
		if s[-1] == s[-2] or s[-2] == wins[s[-1]]:
			dp[-2] = s[-1]
		else:
			dp[-2] = s[-2]
		idx[s[-2]] = n - 2
		for i in range(n - 3, -1, -1):
			idx[s[i]] = i
			j = idx[loses[s[i]]]
			if j != -1:
				dp[i] = dp[j]
			else:
				dp[i] = s[i]
	print(''.join(dp))


N = int(input())
for i in range(N):
	size = int(input())
	str = input()
	res = []
	for i in range(size):
		res.append(' ')
	last_r = '$'
	last_p = '$'
	last_s = '$'
	i = size - 1
	while i >= 0:
		if str[i] == 'R':
			if last_p == '$':
				res[i] = 'R'
			else:
				res[i] = last_p
			last_r = res[i]
		elif str[i] == 'P':
			if last_s == '$':
				res[i] = 'P'
			else:
				res[i] = last_s
			last_p = res[i]
		elif str[i] == 'S':
			if last_r == '$':
				res[i] = 'S'
			else:
				res[i] = last_r
			last_s = res[i]
		i -= 1
	to_print = ''
	for i in range(size):
		to_print += res[i]
	print(to_print)


def match(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'R' and b == 'S' or (a == 'S' and b == 'R'):
		return 'R'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'
	else:
		assert False
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	rdp = [0] * (n + 1)
	sdp = [0] * (n + 1)
	pdp = [0] * (n + 1)
	ans = [0] * (n + 1)
	ans[n] = s[n - 1]
	rdp[n] = match('R', s[n - 1])
	pdp[n] = match('P', s[n - 1])
	sdp[n] = match('S', s[n - 1])
	for i in range(n - 1, 0, -1):
		r_ans = match('R', s[i - 1])
		if r_ans == 'R':
			rdp[i] = rdp[i + 1]
		elif r_ans == 'P':
			rdp[i] = pdp[i + 1]
		elif r_ans == 'S':
			rdp[i] = sdp[i + 1]
		p_ans = match('P', s[i - 1])
		if p_ans == 'R':
			pdp[i] = rdp[i + 1]
		elif p_ans == 'P':
			pdp[i] = pdp[i + 1]
		elif p_ans == 'S':
			pdp[i] = sdp[i + 1]
		s_ans = match('S', s[i - 1])
		if s_ans == 'R':
			sdp[i] = rdp[i + 1]
		elif s_ans == 'P':
			sdp[i] = pdp[i + 1]
		elif s_ans == 'S':
			sdp[i] = sdp[i + 1]
		if s[i - 1] == 'R':
			ans[i] = rdp[i + 1]
		elif s[i - 1] == 'P':
			ans[i] = pdp[i + 1]
		elif s[i - 1] == 'S':
			ans[i] = sdp[i + 1]
	answer = ''.join(map(str, ans[1:]))
	print(str(answer))


def rps(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'S' and b == 'P' or (a == 'P' and b == 'S'):
		return 'S'
	elif a == 'S' and b == 'R' or (a == 'R' and b == 'S'):
		return 'R'
for _ in range(int(input())):
	n = int(input())
	s = input()
	dpr = [0] * n
	dpp = [0] * n
	dps = [0] * n
	ans = [0] * n
	ans[n - 1] = s[n - 1]
	dpr[n - 1] = rps(s[n - 1], 'R')
	dpp[n - 1] = rps(s[n - 1], 'P')
	dps[n - 1] = rps(s[n - 1], 'S')
	for i in range(n - 1, 0, -1):
		win = rps(s[i - 1], 'R')
		if win == 'R':
			dpr[i - 1] = dpr[i]
		elif win == 'P':
			dpr[i - 1] = dpp[i]
		elif win == 'S':
			dpr[i - 1] = dps[i]
		win = rps(s[i - 1], 'P')
		if win == 'R':
			dpp[i - 1] = dpr[i]
		elif win == 'P':
			dpp[i - 1] = dpp[i]
		elif win == 'S':
			dpp[i - 1] = dps[i]
		win = rps(s[i - 1], 'S')
		if win == 'R':
			dps[i - 1] = dpr[i]
		elif win == 'P':
			dps[i - 1] = dpp[i]
		elif win == 'S':
			dps[i - 1] = dps[i]
		if s[i - 1] == 'R':
			ans[i - 1] = dpr[i]
		elif s[i - 1] == 'P':
			ans[i - 1] = dpp[i]
		elif s[i - 1] == 'S':
			ans[i - 1] = dps[i]
	print(''.join(ans))


def string(s, n):
	if s[n - 1] is 'R':
		res1 = 'R'
		res2 = 'P'
	elif s[n - 1] is 'P':
		res1 = 'P'
		res2 = 'S'
	else:
		res1 = 'S'
		res2 = 'R'
	string = s[n - 1]
	d = {}
	d[res1] = 0
	for i in range(1, n):
		if s[n - 1 - i] is 'P':
			if 'S' in d:
				string = string + string[d['S']]
			else:
				string = string + 'P'
			d['P'] = i
		elif s[n - 1 - i] is 'R':
			if 'P' in d:
				string = string + string[d['P']]
			else:
				string = string + 'R'
			d['R'] = i
		elif s[n - 1 - i] is 'S':
			if 'R' in d:
				string = string + string[d['R']]
			else:
				string = string + 'S'
			d['S'] = i
	print(string[::-1])
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	string(s, n)


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		a = input()
		b = [0] * n
		b[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			if a[i] == a[i + 1]:
				b[i] = b[i + 1]
			elif a[i] == 'P' and a[i + 1] == 'S' or (a[i] == 'S' and a[i + 1] == 'R') or (a[i] == 'R' and a[i + 1] == 'P'):
				b[i] = b[i + 1]
			else:
				j = i
				while j < n - 1:
					if a[i] == 'P' and a[j + 1] == 'S' or (a[i] == 'S' and a[j + 1] == 'R') or (a[i] == 'R' and a[j + 1] == 'P') or (a[i] == a[j + 1]):
						b[i] = b[j + 1]
						break
					elif j == n - 2:
						b[i] = a[i]
						j = j + 1
					else:
						j = j + 1
		print(*b, sep='')
except:
	pass


def match(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'R' and b == 'S' or (a == 'S' and b == 'R'):
		return 'R'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'
	else:
		return False
for z in range(int(input())):
	n = int(input())
	s = input()
	dp_r = [''] * (n + 1)
	dp_p = [''] * (n + 1)
	dp_s = [''] * (n + 1)
	ans = [''] * (n + 1)
	ans[n] = s[n - 1]
	dp_r[n] = match('R', s[n - 1])
	dp_p[n] = match('P', s[n - 1])
	dp_s[n] = match('S', s[n - 1])
	for i in range(n - 1, 0, -1):
		r_res = match('R', s[i - 1])
		if r_res == 'R':
			dp_r[i] = dp_r[i + 1]
		elif r_res == 'P':
			dp_r[i] = dp_p[i + 1]
		elif r_res == 'S':
			dp_r[i] = dp_s[i + 1]
		p_res = match('P', s[i - 1])
		if p_res == 'R':
			dp_p[i] = dp_r[i + 1]
		elif p_res == 'P':
			dp_p[i] = dp_p[i + 1]
		elif p_res == 'S':
			dp_p[i] = dp_s[i + 1]
		s_res = match('S', s[i - 1])
		if s_res == 'R':
			dp_s[i] = dp_r[i + 1]
		elif s_res == 'P':
			dp_s[i] = dp_p[i + 1]
		elif s_res == 'S':
			dp_s[i] = dp_s[i + 1]
		if s[i - 1] == 'R':
			ans[i] = dp_r[i + 1]
		elif s[i - 1] == 'P':
			ans[i] = dp_p[i + 1]
		elif s[i - 1] == 'S':
			ans[i] = dp_s[i + 1]
	for i in range(n + 1):
		print(ans[i], end='')
	print()


t = int(input())
myDict = {('S', 'S'): 'S', ('S', 'P'): 'S', ('S', 'R'): 'R', ('P', 'P'): 'P', ('P', 'S'): 'S', ('P', 'R'): 'P', ('R', 'R'): 'R', ('R', 'P'): 'P', ('R', 'S'): 'R'}
while t:
	n = int(input())
	s = input().rstrip()
	R_array = [''] * n
	P_array = [''] * n
	S_array = [''] * n
	ans = [''] * n
	ans[n - 1] = s[n - 1]
	R_array[n - 1] = myDict['R', s[n - 1]]
	P_array[n - 1] = myDict['P', s[n - 1]]
	S_array[n - 1] = myDict['S', s[n - 1]]
	for i in range(n - 2, -1, -1):
		comb = ('R', s[i])
		ansOfFight = myDict[comb]
		if ansOfFight == 'R':
			R_array[i] = R_array[i + 1]
		elif ansOfFight == 'P':
			R_array[i] = P_array[i + 1]
		else:
			R_array[i] = S_array[i + 1]
		comb = ('P', s[i])
		ansOfFight = myDict[comb]
		if ansOfFight == 'R':
			P_array[i] = R_array[i + 1]
		elif ansOfFight == 'P':
			P_array[i] = P_array[i + 1]
		else:
			P_array[i] = S_array[i + 1]
		comb = ('S', s[i])
		ansOfFight = myDict[comb]
		if ansOfFight == 'R':
			S_array[i] = R_array[i + 1]
		elif ansOfFight == 'P':
			S_array[i] = P_array[i + 1]
		else:
			S_array[i] = S_array[i + 1]
		if s[i] == 'R':
			ans[i] = R_array[i]
		elif s[i] == 'P':
			ans[i] = P_array[i]
		else:
			ans[i] = S_array[i]
	for i in range(len(ans)):
		print(ans[i], end='')
	print()
	t -= 1


def Matchfunc(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'R' and b == 'S' or (a == 'S' and b == 'R'):
		return 'R'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'
	else:
		return False
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	rock = [None] * (n + 1)
	scissor = [None] * (n + 1)
	paper = [None] * (n + 1)
	ans_str = [None] * (n + 1)
	ans_str[n] = s[n - 1]
	rock[n] = Matchfunc('R', s[n - 1])
	paper[n] = Matchfunc('P', s[n - 1])
	scissor[n] = Matchfunc('S', s[n - 1])
	for i in range(n - 1, 0, -1):
		rock_result = Matchfunc('R', s[i - 1])
		if rock_result == 'R':
			rock[i] = rock[i + 1]
		elif rock_result == 'P':
			rock[i] = paper[i + 1]
		elif rock_result == 'S':
			rock[i] = scissor[i + 1]
		paper_result = Matchfunc('P', s[i - 1])
		if paper_result == 'R':
			paper[i] = rock[i + 1]
		elif paper_result == 'P':
			paper[i] = paper[i + 1]
		elif paper_result == 'S':
			paper[i] = scissor[i + 1]
		scissor_result = Matchfunc('S', s[i - 1])
		if scissor_result == 'R':
			scissor[i] = rock[i + 1]
		elif scissor_result == 'P':
			scissor[i] = paper[i + 1]
		elif scissor_result == 'S':
			scissor[i] = scissor[i + 1]
		if s[i - 1] == 'R':
			ans_str[i] = rock[i + 1]
		elif s[i - 1] == 'P':
			ans_str[i] = paper[i + 1]
		elif s[i - 1] == 'S':
			ans_str[i] = scissor[i + 1]
	final_ans = ''
	for i in range(1, n + 1):
		final_ans = final_ans + ans_str[i]
	print(final_ans)


t = int(input())
l = []
while t > 0:
	n = int(input())
	mov = list(map(str, input()))
	r = {}
	p = {}
	s = {}
	S = ''
	if n == 1:
		l.append(mov[0])
	else:
		S += mov[n - 1]
		if mov[n - 1] == 'R':
			r[n - 2] = 'R'
			p[n - 2] = 'P'
			s[n - 2] = 'R'
		elif mov[n - 1] == 'P':
			r[n - 2] = 'P'
			p[n - 2] = 'P'
			s[n - 2] = 'S'
		elif mov[n - 1] == 'S':
			r[n - 2] = 'R'
			p[n - 2] = 'S'
			s[n - 2] = 'S'
		if mov[n - 2] == 'R':
			S += r[n - 2]
		elif mov[n - 2] == 'P':
			S += p[n - 2]
		else:
			S += s[n - 2]
		for i in range(n - 3, -1, -1):
			if mov[i + 1] == 'R':
				r[i] = r[i + 1]
				p[i] = p[i + 1]
				s[i] = r[i + 1]
			elif mov[i + 1] == 'P':
				r[i] = p[i + 1]
				p[i] = p[i + 1]
				s[i] = s[i + 1]
			elif mov[i + 1] == 'S':
				r[i] = r[i + 1]
				p[i] = s[i + 1]
				s[i] = s[i + 1]
			if mov[i] == 'P':
				S += p[i]
			elif mov[i] == 'R':
				S += r[i]
			else:
				S += s[i]
		l.append(S[::-1])
	t -= 1
print('\n'.join(l))


def ans(l):
	if l[-1] == l[-2]:
		return l[-1]
	if l == ['P', 'R']:
		return 'P'
	if l == ['R', 'S']:
		return 'R'
	if l == ['P', 'S']:
		return 'S'
for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s[-1]
	b = ''
	for i in range(n - 2, -1, -1):
		if a != s[i]:
			b = s[i]
			break
	if b == '':
		print(n * a)
	elif a == 'P' and b == 'R':
		print(n * 'P')
	elif a == 'R' and b == 'S':
		print(n * 'R')
	elif a == 'S' and b == 'P':
		print(n * 'S')
	else:
		c = d = o = ''
		c_ = n - 1
		p = True
		y = c_
		k = {}
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				c = s[i]
				o += s[i]
			elif d == '':
				if c != s[i]:
					d = s[i]
				o += s[i]
			elif (s[i] == c or s[i] == d) and p is True:
				o += d
				if s[i] == c:
					y = i
			elif (s[i] != c and s[i] != d) and p is True:
				r = s[i]
				if y == n - 1:
					o += c
					p = False
					k[s[i]] = c
				else:
					o += d
					p = False
					k[s[i]] = d
			elif s[i] == r:
				if k.get(c, 0) == 0:
					o += k[s[i]]
				else:
					o += k[c]
					k[s[i]] = k[c]
			elif s[i] == d:
				o += k[r]
				k[s[i]] = k[r]
			elif s[i] == c:
				if not k.get(d, 0):
					k[s[i]] = d
					o += d
				else:
					o += k[d]
					k[s[i]] = k[d]
		print(o[::-1])


def match(a, b):
	if a == b:
		return a
	elif a == 'R' and b == 'P' or (a == 'P' and b == 'R'):
		return 'P'
	elif a == 'R' and b == 'S' or (a == 'S' and b == 'R'):
		return 'R'
	elif a == 'P' and b == 'S' or (a == 'S' and b == 'P'):
		return 'S'

def main():
	t = int(input())
	for j in range(t):
		n = int(input())
		s = input()
		res = ''
		dp_r = [0] * (n + 1)
		dp_p = [0] * (n + 1)
		dp_s = [0] * (n + 1)
		ans = [0] * (n + 1)
		ans[n] = s[n - 1]
		dp_r[n] = match('R', s[n - 1])
		dp_p[n] = match('P', s[n - 1])
		dp_s[n] = match('S', s[n - 1])
		for i in range(n - 1, 0, -1):
			r_res = match('R', s[i - 1])
			if r_res == 'R':
				dp_r[i] = dp_r[i + 1]
			elif r_res == 'P':
				dp_r[i] = dp_p[i + 1]
			elif r_res == 'S':
				dp_r[i] = dp_s[i + 1]
			p_res = match('P', s[i - 1])
			if p_res == 'R':
				dp_p[i] = dp_r[i + 1]
			elif p_res == 'P':
				dp_p[i] = dp_p[i + 1]
			elif p_res == 'S':
				dp_p[i] = dp_s[i + 1]
			s_res = match('S', s[i - 1])
			if s_res == 'R':
				dp_s[i] = dp_r[i + 1]
			elif s_res == 'P':
				dp_s[i] = dp_p[i + 1]
			elif s_res == 'S':
				dp_s[i] = dp_s[i + 1]
			if s[i - 1] == 'R':
				ans[i] = dp_r[i + 1]
			elif s[i - 1] == 'P':
				ans[i] = dp_p[i + 1]
			elif s[i - 1] == 'S':
				ans[i] = dp_s[i + 1]
		for val in ans:
			if val != 0:
				res += val
		print(res)
main()


choices = {'R': ['R', 'S', 'P'], 'P': ['P', 'R', 'S'], 'S': ['S', 'P', 'R']}
for test in range(int(input())):
	N = int(input())
	S = input()
	first_answer = S[-1]
	second_answer = choices[first_answer][2]
	current_answer = first_answer
	same = False
	final_string_list = [first_answer]
	for x in range(N - 1):
		if same == True:
			final_string_list.append(current_answer)
		elif S[-x - 2] == choices[S[-x - 1]][0]:
			final_string_list.append(current_answer)
		elif S[-x - 2] == choices[S[-x - 1]][1]:
			final_string_list.append(current_answer)
			same = True
		elif S[-x - 2] == choices[S[-x - 1]][2]:
			if current_answer == first_answer:
				current_answer = second_answer
			elif current_answer == second_answer:
				current_answer = first_answer
			final_string_list.append(current_answer)
	final_string_list = [final_string_list[-1 - x] for x in range(len(final_string_list))]
	final_string = ''.join(final_string_list)
	print(final_string)


def is_won(p1, p2):
	result = False
	if p1 == 'R':
		result = p2 == 'S'
	elif p1 == 'P':
		result = p2 == 'R'
	else:
		result = p2 == 'P'
	return result

def testcase():

	def roll_win(plyr_idx, opp_idx):
		result = S[plyr_idx]
		while opp_idx < N and is_won(S[plyr_idx], S[opp_idx]):
			opp_idx += 1
		if opp_idx < N:
			result = R[opp_idx]
		return result
	N = int(input())
	S = input()
	R = [None for s in S]
	R[N - 1] = S[N - 1]
	for i in range(N - 2, -1, -1):
		R[i] = roll_win(i, i + 2) if is_won(S[i], S[i + 1]) else R[i + 1]
	return ''.join(R)
for i in range(int(input())):
	print(testcase())


import numpy as np

def who_won(player_1, player_2):
	if player_2 == 'P' and player_1 == 'R' or (player_2 == 'S' and player_1 == 'P') or (player_2 == 'R' and player_1 == 'S'):
		return player_2
	else:
		return player_1
numberOfTests = int(input())
results = []
for x in range(numberOfTests):
	n = int(input())
	gameString = input()
	R = ['' for x in range(n)]
	P = ['' for x in range(n)]
	S = ['' for x in range(n)]
	res = ['' for x in range(n)]
	res[n - 1] = gameString[n - 1]
	R[n - 1] = who_won('R', gameString[n - 1])
	P[n - 1] = who_won('P', gameString[n - 1])
	S[n - 1] = who_won('S', gameString[n - 1])
	for i in range(n - 2, -1, -1):
		temp = who_won('R', gameString[i])
		if temp == 'R':
			R[i] = R[i + 1]
		elif temp == 'P':
			R[i] = P[i + 1]
		else:
			R[i] = S[i + 1]
		temp = who_won('P', gameString[i])
		if temp == 'R':
			P[i] = R[i + 1]
		elif temp == 'P':
			P[i] = P[i + 1]
		else:
			P[i] = S[i + 1]
		temp = who_won('S', gameString[i])
		if temp == 'R':
			S[i] = R[i + 1]
		elif temp == 'P':
			S[i] = P[i + 1]
		else:
			S[i] = S[i + 1]
		temp = gameString[i]
		if temp == 'R':
			res[i] = R[i + 1]
		elif temp == 'P':
			res[i] = P[i + 1]
		else:
			res[i] = S[i + 1]
	result = ''
	print(result.join(res))


def move_is_rock(move2):
	if move2 == 'P':
		return 'P'
	elif move2 == 'S':
		return 'R'

def move_is_paper(move2):
	if move2 == 'S':
		return 'S'
	elif move2 == 'R':
		return 'P'

def move_is_scissor(move2):
	if move2 == 'R':
		return 'R'
	elif move2 == 'P':
		return 'S'

def single_match(move1, move2):
	if move1 == move2:
		return move1
	elif move1 == 'R':
		return move_is_rock(move2)
	elif move1 == 'P':
		return move_is_paper(move2)
	elif move1 == 'S':
		return move_is_scissor(move2)
	else:
		exit()

def templated_check(sign_RPS, s_moves, i, dest_array, rock_array, paper_array, scissor_array):
	result = single_match(sign_RPS, s_moves[i - 1])
	if result == 'R':
		dest_array[i] = rock_array[i + 1]
	elif result == 'P':
		dest_array[i] = paper_array[i + 1]
	elif result == 'S':
		dest_array[i] = scissor_array[i + 1]
tests = int(input())
for test in range(tests):
	number_of_players = int(input())
	s_moves = input()
	rock_array = [''] * (number_of_players + 1)
	paper_array = [''] * (number_of_players + 1)
	scissor_array = [''] * (number_of_players + 1)
	answer_array = [''] * (number_of_players + 1)
	answer_array[number_of_players] = s_moves[number_of_players - 1]
	rock_array[number_of_players] = single_match('R', s_moves[number_of_players - 1])
	paper_array[number_of_players] = single_match('P', s_moves[number_of_players - 1])
	scissor_array[number_of_players] = single_match('S', s_moves[number_of_players - 1])
	for i in range(number_of_players - 1, 0, -1):
		templated_check('R', s_moves, i, rock_array, rock_array, paper_array, scissor_array)
		templated_check('P', s_moves, i, paper_array, rock_array, paper_array, scissor_array)
		templated_check('S', s_moves, i, scissor_array, rock_array, paper_array, scissor_array)
		paper_result = single_match('P', s_moves[i - 1])
		if s_moves[i - 1] == 'R':
			answer_array[i] = rock_array[i + 1]
		elif s_moves[i - 1] == 'P':
			answer_array[i] = paper_array[i + 1]
		elif s_moves[i - 1] == 'S':
			answer_array[i] = scissor_array[i + 1]
	for i in range(1, number_of_players + 1):
		print(answer_array[i], end='')
	print()


R = 0
P = 1
S = 2
for _ in range(int(input())):
	input()
	moves = []
	for c in input():
		if c == 'R':
			moves.append(R)
		elif c == 'P':
			moves.append(P)
		else:
			moves.append(S)
	N = len(moves)
	W = [-1] * N
	W[-1] = moves[-1]
	last = [N + 1] * 3
	last[moves[-1]] = N - 1
	for i in range(N - 2, -1, -1):
		if moves[i] == moves[i + 1] or (moves[i] + 1) % 3 == moves[i + 1]:
			W[i] = W[i + 1]
		else:
			nextdiff = min(last[moves[i]], last[(moves[i] + 1) % 3])
			if nextdiff > N:
				W[i] = moves[i]
			else:
				W[i] = W[nextdiff]
		last[moves[i]] = i
	for move in W:
		if move == R:
			print('R', end='')
		elif move == P:
			print('P', end='')
		else:
			print('S', end='')
	print()


def logic(list, N):
	complementary = {'P': 'S', 'R': 'P', 'S': 'R'}
	answer = ''
	if N == 1:
		answer = answer + list[0]
	else:
		stop = False
		unnecessary = 0
		flipped = True
		for i in range(N - 1):
			if list[N - 1 - i] + list[N - 2 - i] == 'SP' or list[N - 1 - i] + list[N - 2 - i] == 'PR' or list[N - 1 - i] + list[N - 2 - i] == 'RS':
				stop = True
				unnecessary = i + 1
			elif list[N - 1 - i] + list[N - 2 - i] == 'PS' or list[N - 1 - i] + list[N - 2 - i] == 'RP' or list[N - 1 - i] + list[N - 2 - i] == 'SR':
				flipped = not flipped
			if stop:
				break
		if stop:
			for i in range(N - unnecessary):
				if flipped:
					answer = answer + list[len(list) - 1]
					list = list[1:]
				else:
					answer = answer + complementary[list[len(list) - 1]]
					list = list[1:]
			for i in range(unnecessary - 1):
				if flipped:
					answer = answer + list[len(list) - 1]
				else:
					answer = answer + complementary[list[len(list) - 1]]
				if list[0] != list[1]:
					flipped = not flipped
				list = list[1:]
		else:
			for i in range(N - 1):
				if flipped:
					answer = answer + list[len(list) - 1]
				else:
					answer = answer + complementary[list[len(list) - 1]]
				if list[0] != list[1]:
					flipped = not flipped
				list = list[1:]
		answer = answer + list[0]
	return answer
T = int(input())
for i in range(T):
	N = int(input())
	moves = input()
	print(logic(moves, N))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(s)
		continue
	s1 = s[n - 1]
	for j in range(n - 2, -1, -1):
		temp = s[j]
		index = -1
		for k in range(j + 1, n):
			if temp == s[k]:
				index = k
				break
			elif temp == 'R' and s[k] == 'P':
				index = k
				break
			elif temp == 'P' and s[k] == 'S':
				index = k
				break
			elif temp == 'S' and s[k] == 'R':
				index = k
				break
		if index != -1:
			s1 = s1[k - j - 1] + s1
		else:
			s1 = temp + s1
	print(s1)


def checker(v1, v2):
	if v1 == v2:
		return v1
	if v1 == 'S' and v2 == 'R' or (v1 == 'R' and v2 == 'P') or (v1 == 'P' and v2 == 'S'):
		return v2
	if v1 == 'R' and v2 == 'S' or (v1 == 'P' and v2 == 'R') or (v1 == 'S' and v2 == 'P'):
		return v1

def solution(ls: list):
	n = len(ls)
	dp_r = [0] * (n + 1)
	dp_p = [0] * (n + 1)
	dp_s = [0] * (n + 1)
	ans = [0] * (n + 1)
	ans[n] = ls[n - 1]
	dp_r[n] = checker('R', ls[n - 1])
	dp_p[n] = checker('P', ls[n - 1])
	dp_s[n] = checker('S', ls[n - 1])
	for i in range(n - 1, 0, -1):
		r_res = checker('R', ls[i - 1])
		if r_res == 'R':
			dp_r[i] = dp_r[i + 1]
		elif r_res == 'P':
			dp_r[i] = dp_p[i + 1]
		else:
			dp_r[i] = dp_s[i + 1]
		p_res = checker('P', ls[i - 1])
		if p_res == 'R':
			dp_p[i] = dp_r[i + 1]
		elif p_res == 'P':
			dp_p[i] = dp_p[i + 1]
		else:
			dp_p[i] = dp_s[i + 1]
		s_res = checker('S', ls[i - 1])
		if s_res == 'R':
			dp_s[i] = dp_r[i + 1]
		elif s_res == 'P':
			dp_s[i] = dp_p[i + 1]
		else:
			dp_s[i] = dp_s[i + 1]
		if ls[i - 1] == 'R':
			ans[i] = dp_r[i + 1]
		elif ls[i - 1] == 'P':
			ans[i] = dp_p[i + 1]
		else:
			ans[i] = dp_s[i + 1]
	for i in range(1, n + 1):
		print(ans[i], end='')
	print()
t = int(input())
while t:
	n = int(input())
	string = list(input())
	solution(string)
	t -= 1


def match(a, b):
	if a == b:
		return a
	if a == 'S' and b == 'R' or (a == 'R' and b == 'S'):
		return 'R'
	elif a == 'S' and b == 'P' or (a == 'P' and b == 'S'):
		return 'S'
	elif a == 'P' and b == 'R' or (a == 'R' and b == 'P'):
		return 'P'
	else:
		return None
for _ in range(int(input())):
	n = int(input())
	s = input()
	dp_r = [None] * (n + 1)
	dp_p = [None] * (n + 1)
	dp_s = [None] * (n + 1)
	ans = [None] * (n + 1)
	ans[n] = s[n - 1]
	dp_r[n] = match('R', s[n - 1])
	dp_p[n] = match('P', s[n - 1])
	dp_s[n] = match('S', s[n - 1])
	for i in range(n - 1, 1 - 1, -1):
		r_res = match('R', s[i - 1])
		if r_res == 'R':
			dp_r[i] = dp_r[i + 1]
		elif r_res == 'P':
			dp_r[i] = dp_p[i + 1]
		elif r_res == 'S':
			dp_r[i] = dp_s[i + 1]
		p_res = match('P', s[i - 1])
		if p_res == 'R':
			dp_p[i] = dp_r[i + 1]
		elif p_res == 'P':
			dp_p[i] = dp_p[i + 1]
		elif p_res == 'S':
			dp_p[i] = dp_s[i + 1]
		s_res = match('S', s[i - 1])
		if s_res == 'R':
			dp_s[i] = dp_r[i + 1]
		elif s_res == 'P':
			dp_s[i] = dp_p[i + 1]
		elif s_res == 'S':
			dp_s[i] = dp_s[i + 1]
		if s[i - 1] == 'R':
			ans[i] = dp_r[i + 1]
		elif s[i - 1] == 'P':
			ans[i] = dp_p[i + 1]
		elif s[i - 1] == 'S':
			ans[i] = dp_s[i + 1]
	print(''.join(ans[1:]))


def win(pl1, pl2):
	game = pl1 + pl2
	if game == 'SR' or game == 'PS' or game == 'RP' or (pl1 == pl2):
		return False
	return True

def SPQR(s):
	if len(s) == 1:
		return s
	res = s[0]
	order = [(s[0], 0)]
	for i in range(1, len(s)):
		winAll = True
		for ordr in order:
			if win(ordr[0], s[i]):
				res += res[ordr[1]]
				winAll = False
				break
		if winAll:
			res += s[i]
		if s[i] != order[0][0]:
			order.insert(0, (s[i], i))
	return res[::-1]
T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	print(SPQR(S[::-1]))


def foofafoofa(one, two):
	if one == two:
		return one
	elif one == 'R' and two == 'P' or (one == 'P' and two == 'R'):
		return 'P'
	elif one == 'R' and two == 'S' or (one == 'S' and two == 'R'):
		return 'R'
	elif one == 'S' and two == 'P' or (one == 'P' and two == 'S'):
		return 'S'
	else:
		return False
N = int(input())
for _ in range(N):
	n = int(input())
	s = input()
	dpRock = [' ' for i in range(n + 1)]
	dpPaper = [' ' for i in range(n + 1)]
	dpScissors = [' ' for i in range(n + 1)]
	output = [' ' for i in range(n + 1)]
	output[n] = s[n - 1]
	dpRock[n] = foofafoofa('R', s[n - 1])
	dpPaper[n] = foofafoofa('P', s[n - 1])
	dpScissors[n] = foofafoofa('S', s[n - 1])
	for i in range(n - 1, 0, -1):
		r_res = foofafoofa('R', s[i - 1])
		if r_res == 'R':
			dpRock[i] = dpRock[i + 1]
		elif r_res == 'S':
			dpRock[i] = dpScissors[i + 1]
		elif r_res == 'P':
			dpRock[i] = dpPaper[i + 1]
		p_res = foofafoofa('P', s[i - 1])
		if p_res == 'R':
			dpPaper[i] = dpRock[i + 1]
		elif p_res == 'S':
			dpPaper[i] = dpScissors[i + 1]
		elif p_res == 'P':
			dpPaper[i] = dpPaper[i + 1]
		s_res = foofafoofa('S', s[i - 1])
		if s_res == 'R':
			dpScissors[i] = dpRock[i + 1]
		elif s_res == 'S':
			dpScissors[i] = dpScissors[i + 1]
		elif s_res == 'P':
			dpScissors[i] = dpPaper[i + 1]
		if s[i - 1] == 'R':
			output[i] = dpRock[i + 1]
		elif s[i - 1] == 'P':
			output[i] = dpPaper[i + 1]
		else:
			output[i] = dpScissors[i + 1]
	for i in range(n + 1):
		if output[i] != ' ':
			print(output[i], end='')
	print()


def rps(a, b):
	if a == 'R' and b == 'R' or (a == 'P' and b == 'P') or (a == 'S' and b == 'S') or (a == 'R' and b == 'S') or (a == 'S' and b == 'P') or (a == 'P' and b == 'R'):
		return a
	else:
		return b
for i in range(int(input())):
	n = int(input())
	s = input()
	k = [0]
	k[0] = s[n - 1]
	for j in range(n - 2, -1, -1):
		l = j + 1
		c = 0
		m = s[j]
		while 1:
			if rps(m, s[l]) == s[l] and l != n - 1:
				k.append(k[-c - 1])
				break
			elif l == n - 1:
				k.append(rps(m, s[l]))
				break
			else:
				m = rps(m, s[l])
				c += 1
				l += 1
	s = ''.join(k)
	print(s[::-1])


T = int(input())
for t in range(T):
	N = int(input())
	ropasci = input()
	reString = [None] * N
	reString[N - 1] = ropasci[N - 1]
	s = p = r = -1
	if ropasci[N - 1] == 'P':
		p = N - 1
	elif ropasci[N - 1] == 'R':
		r = N - 1
	else:
		s = N - 1
	for i in range(len(ropasci) - 2, -1, -1):
		if ropasci[i] == 'P':
			p = i
			if s != -1:
				reString[i] = reString[s]
			else:
				reString[i] = ropasci[i]
		elif ropasci[i] == 'S':
			s = i
			if r != -1:
				reString[i] = reString[r]
			else:
				reString[i] = ropasci[i]
		elif ropasci[i] == 'R':
			r = i
			if p != -1:
				reString[i] = reString[p]
			else:
				reString[i] = ropasci[i]
	reString = ''.join(map(str, reString))
	print(reString)


def one_game(first, second):
	if first == second:
		return first
	if first == 'P' and second == 'R' or (first == 'R' and second == 'P'):
		return 'P'
	if first == 'R' and second == 'S' or (first == 'S' and second == 'R'):
		return 'R'
	if first == 'S' and second == 'P' or (first == 'P' and second == 'S'):
		return 'S'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	rock = [None] * (n + 1)
	paper = [None] * (n + 1)
	scissors = [None] * (n + 1)
	result_str = [None] * (n + 1)
	result_str[n] = s[n - 1]
	rock[n] = one_game('R', s[n - 1])
	paper[n] = one_game('P', s[n - 1])
	scissors[n] = one_game('S', s[n - 1])
	for i in range(n - 1, 0, -1):
		rock_result = one_game('R', s[i - 1])
		if rock_result == 'R':
			rock[i] = rock[i + 1]
		elif rock_result == 'P':
			rock[i] = paper[i + 1]
		else:
			rock[i] = scissors[i + 1]
		paper_result = one_game('P', s[i - 1])
		if paper_result == 'R':
			paper[i] = rock[i + 1]
		elif paper_result == 'P':
			paper[i] = paper[i + 1]
		else:
			paper[i] = scissors[i + 1]
		scissors_result = one_game('S', s[i - 1])
		if scissors_result == 'R':
			scissors[i] = rock[i + 1]
		elif scissors_result == 'P':
			scissors[i] = paper[i + 1]
		else:
			scissors[i] = scissors[i + 1]
		if s[i - 1] == 'R':
			result_str[i] = rock[i + 1]
		elif s[i - 1] == 'P':
			result_str[i] = paper[i + 1]
		else:
			result_str[i] = scissors[i + 1]
	for i in range(1, n + 1, 1):
		print(result_str[i], end='')
	print()


def getWinner(tuple_):
	if tuple_[0] == tuple_[1]:
		return tuple_[0]
	elif 'S' in tuple_ and 'P' in tuple_:
		return 'S'
	elif 'S' in tuple_ and 'R' in tuple_:
		return 'R'
	else:
		return 'P'

def printWinners(si, n):
	mat_r = ['X' for i in range(n + 1)]
	mat_p = mat_r.copy()
	mat_s = mat_r.copy()
	ans = mat_r.copy()
	ans[n] = si[n - 1]
	mat_r[n] = getWinner(('R', si[n - 1]))
	mat_p[n] = getWinner(('P', si[n - 1]))
	mat_s[n] = getWinner(('S', si[n - 1]))
	for i in range(n - 1, 0, -1):
		r_res = getWinner(('R', si[i - 1]))
		if r_res == 'R':
			mat_r[i] = mat_r[i + 1]
		elif r_res == 'P':
			mat_r[i] = mat_p[i + 1]
		else:
			mat_r[i] = mat_s[i + 1]
		p_res = getWinner(('P', si[i - 1]))
		if p_res == 'R':
			mat_p[i] = mat_r[i + 1]
		elif p_res == 'P':
			mat_p[i] = mat_p[i + 1]
		else:
			mat_p[i] = mat_s[i + 1]
		s_res = getWinner(('S', si[i - 1]))
		if s_res == 'R':
			mat_s[i] = mat_r[i + 1]
		elif s_res == 'P':
			mat_s[i] = mat_p[i + 1]
		else:
			mat_s[i] = mat_s[i + 1]
		if si[i - 1] == 'R':
			ans[i] = mat_r[i + 1]
		elif si[i - 1] == 'P':
			ans[i] = mat_p[i + 1]
		else:
			ans[i] = mat_s[i + 1]
	return ''.join(ans[1:])
for _ in range(int(input())):
	n = int(input())
	si = input()
	print(printWinners(si, n))


ROCK_SIGN = 'R'
PAPER_SIGN = 'P'
SCCISORS_SIGN = 'S'

def make_turn(player1, player2):
	if player1 == player2:
		return player1
	if player1 == ROCK_SIGN and player2 == SCCISORS_SIGN or (player1 == SCCISORS_SIGN and player2 == ROCK_SIGN):
		return ROCK_SIGN
	if player1 == ROCK_SIGN and player2 == PAPER_SIGN or (player1 == PAPER_SIGN and player2 == ROCK_SIGN):
		return PAPER_SIGN
	if player1 == SCCISORS_SIGN and player2 == PAPER_SIGN or (player1 == PAPER_SIGN and player2 == SCCISORS_SIGN):
		return SCCISORS_SIGN
T = int(input())
for _ in range(T):
	numberOfPlayers = int(input())
	input_str = input()
	res = [' '] * (numberOfPlayers + 1)
	rock = [' '] * (numberOfPlayers + 1)
	paper = [' '] * (numberOfPlayers + 1)
	sccisors = [' '] * (numberOfPlayers + 1)
	res[numberOfPlayers] = input_str[numberOfPlayers - 1]
	rock[numberOfPlayers] = make_turn(ROCK_SIGN, input_str[numberOfPlayers - 1])
	paper[numberOfPlayers] = make_turn(PAPER_SIGN, input_str[numberOfPlayers - 1])
	sccisors[numberOfPlayers] = make_turn(SCCISORS_SIGN, input_str[numberOfPlayers - 1])
	for i in range(numberOfPlayers - 1, 0, -1):
		iPlusOne = i + 1
		r_play = make_turn(ROCK_SIGN, input_str[i - 1])
		if r_play == ROCK_SIGN:
			rock[i] = rock[iPlusOne]
		elif r_play == PAPER_SIGN:
			rock[i] = paper[iPlusOne]
		elif r_play == SCCISORS_SIGN:
			rock[i] = sccisors[iPlusOne]
		p_play = make_turn(PAPER_SIGN, input_str[i - 1])
		if p_play == ROCK_SIGN:
			paper[i] = rock[iPlusOne]
		elif p_play == PAPER_SIGN:
			paper[i] = paper[iPlusOne]
		elif p_play == SCCISORS_SIGN:
			paper[i] = sccisors[iPlusOne]
		s_play = make_turn(SCCISORS_SIGN, input_str[i - 1])
		if s_play == ROCK_SIGN:
			sccisors[i] = rock[iPlusOne]
		elif s_play == PAPER_SIGN:
			sccisors[i] = paper[iPlusOne]
		elif s_play == SCCISORS_SIGN:
			sccisors[i] = sccisors[iPlusOne]
		if input_str[i - 1] == ROCK_SIGN:
			res[i] = rock[iPlusOne]
		elif input_str[i - 1] == PAPER_SIGN:
			res[i] = paper[iPlusOne]
		elif input_str[i - 1] == SCCISORS_SIGN:
			res[i] = sccisors[iPlusOne]
	for i in range(1, numberOfPlayers + 1):
		print(res[i], end='')
	print()


for _ in range(int(input())):
	n = int(input())
	string = input()
	(P, R, S) = (-1, -1, -1)
	res_arr = list(string[:])
	if string[-1] == 'P':
		P = n - 1
	elif string[-1] == 'R':
		R = n - 1
	else:
		S = n - 1
	for i in range(n - 2, -1, -1):
		if string[i] == 'P':
			P = i
			if S != -1:
				res_arr[i] = res_arr[S]
			else:
				res_arr[i] = string[i]
		elif string[i] == 'S':
			S = i
			if R != -1:
				res_arr[i] = res_arr[R]
			else:
				res_arr[i] = string[i]
		elif string[i] == 'R':
			R = i
			if P != -1:
				res_arr[i] = res_arr[P]
			else:
				res_arr[i] = string[i]
	new_string = ''.join(res_arr)
	print(new_string)