CF1380B.Universal Solution

Recently, you found a bot to play "Rock paper scissors" with. Unfortunately, the bot uses quite a simple algorithm to play: he has a string $s = s_1 s_2 \dots s_{n}$ of length $n$ where each letter is either R, S or P.

While initializing, the bot is choosing a starting index $pos$ ($1 \le pos \le n$), and then it can play any number of rounds. In the first round, he chooses "Rock", "Scissors" or "Paper" based on the value of $s_{pos}$:

• if $s_{pos}$ is equal to R the bot chooses "Rock";
• if $s_{pos}$ is equal to S the bot chooses "Scissors";
• if $s_{pos}$ is equal to P the bot chooses "Paper";

In the second round, the bot's choice is based on the value of $s_{pos + 1}$. In the third round — on $s_{pos + 2}$ and so on. After $s_n$ the bot returns to $s_1$ and continues his game.

You plan to play $n$ rounds and you've already figured out the string $s$ but still don't know what is the starting index $pos$. But since the bot's tactic is so boring, you've decided to find $n$ choices to each round to maximize the average number of wins.

In other words, let's suggest your choices are $c_1 c_2 \dots c_n$ and if the bot starts from index $pos$ then you'll win in $win(pos)$ rounds. Find $c_1 c_2 \dots c_n$ such that $\frac{win(1) + win(2) + \dots + win(n)}{n}$ is maximum possible.

最近，你发现了一个可以和你玩“石头剪刀布”的机器人。不幸的是，这个机器人采用了一种非常简单的算法：它拥有一串长度为 $n$ 的字符串 $s = s_1 s_2 \dots s_{n}$，其中每个字符均为 R、S 或 P。

在初始化阶段，机器人会选定一个起始索引 $pos$（满足 $1 \le pos \le n$），之后它可以进行任意轮数的游戏。在第 1 轮中，机器人根据 $s_{pos}$ 的值选择“石头”、“剪刀”或“布”：

• 若 $s_{pos} = \text{R}$，则机器人选择“石头”；
• 若 $s_{pos} = \text{S}$，则机器人选择“剪刀”；
• 若 $s_{pos} = \text{P}$，则机器人选择“布”。

在第 2 轮中，机器人的选择依据为 $s_{pos + 1}$；在第 3 轮中，依据为 $s_{pos + 2}$，依此类推。当到达 $s_n$ 后，机器人将循环回到 $s_1$ 并继续游戏。

你计划进行 $n$ 轮游戏，且已知字符串 $s$，但尚不清楚机器人的起始索引 $pos$ 是多少。然而，由于该机器人的策略过于单调乏味，你决定预先确定自己在每一轮中的出拳 $c_1 c_2 \dots c_n$，以最大化获胜轮数的平均值。

换言之，假设你的出拳序列为 $c_1 c_2 \dots c_n$，若机器人从索引 $pos$ 开始，则你在该情形下将赢得 $win(pos)$ 轮。请找出序列 $c_1 c_2 \dots c_n$，使得 $\frac{win(1) + win(2) + \dots + win(n)}{n}$ 达到可能的最大值。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Next $t$ lines contain test cases — one per line. The first and only line of each test case contains string $s = s_1 s_2 \dots s_{n}$ ($1 \le n \le 2 \cdot 10^5$; $s_i \in {\text{R}, \text{S}, \text{P}}$) — the string of the bot.

It's guaranteed that the total length of all strings in one test doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

接下来的 $t$ 行为测试用例，每行一个。每个测试用例仅有一行，包含一个字符串 $s = s_1 s_2 \dots s_{n}$（$1 \le n \le 2 \cdot 10^5$；$s_i \in \{\text{R}, \text{S}, \text{P}\}$）—— 表示该机器人的出拳序列。

保证单次测试中所有字符串的总长度不超过 $2 \cdot 10^5$。

For each test case, print $n$ choices $c_1 c_2 \dots c_n$ to maximize the average number of wins. Print them in the same manner as the string $s$.

If there are multiple optimal answers, print any of them.

对于每个测试用例，输出 $n$ 个选择 $c_1 c_2 \dots c_n$，以最大化获胜次数的平均值。输出格式需与字符串 $s$ 相同。

若存在多个最优解，输出任意一个即可。

In the first test case, the bot (wherever it starts) will always choose "Rock", so we can always choose "Paper". So, in any case, we will win all $n = 4$ rounds, so the average is also equal to $4$.

In the second test case:

• if bot will start from $pos = 1$, then $(s_1, c_1)$ is draw, $(s_2, c_2)$ is draw and $(s_3, c_3)$ is draw, so $win(1) = 0$;
• if bot will start from $pos = 2$, then $(s_2, c_1)$ is win, $(s_3, c_2)$ is win and $(s_1, c_3)$ is win, so $win(2) = 3$;
• if bot will start from $pos = 3$, then $(s_3, c_1)$ is lose, $(s_1, c_2)$ is lose and $(s_2, c_3)$ is lose, so $win(3) = 0$;

The average is equal to $\frac{0 + 3 + 0}{3} = 1$ and it can be proven that it's the maximum possible average.

A picture from Wikipedia explaining "Rock paper scissors" game:

在第一个测试用例中，机器人（无论从何处开始）总会选择“石头”，因此我们总可以选择“布”。于是，在任何情况下，我们都将赢得全部 $n = 4$ 轮，故平均值也为 $4$。

在第二个测试用例中：

• 若机器人从 $pos = 1$ 开始，则 $(s_1, c_1)$ 为平局，$(s_2, c_2)$ 为平局，$(s_3, c_3)$ 为平局，因此 $win(1) = 0$；
• 若机器人从 $pos = 2$ 开始，则 $(s_2, c_1)$ 为获胜，$(s_3, c_2)$ 为获胜，$(s_1, c_3)$ 为获胜，因此 $win(2) = 3$；
• 若机器人从 $pos = 3$ 开始，则 $(s_3, c_1)$ 为失败，$(s_1, c_2)$ 为失败，$(s_2, c_3)$ 为失败，因此 $win(3) = 0$；

平均值为 $\frac{0 + 3 + 0}{3} = 1$，且可以证明这是可能达到的最大平均值。

维基百科中解释“石头剪刀布”游戏的一张图片：