CF1380B Universal Solution

最近，你发现了一个可以和你玩“石头剪刀布”的机器人。不幸的是，这个机器人采用了非常简单的算法：它有一个长度为 $n$ 的字符串 $s = s_1 s_2 \dots s_n$，其中每个字母都是 R、S 或 P。 初始化时，机器人会选择一个起始下标 $pos$（$1 \le pos \le n$），然后可以进行任意多轮游戏。在第一轮中，它根据 $s_{pos}$ 的值选择“石头”、“剪刀”或“布”： - 如果 $s_{pos}$ 等于 R，机器人选择“石头”； - 如果 $s_{pos}$ 等于 S，机器人选择“剪刀”； - 如果 $s_{pos}$ 等于 P，机器人选择“布”； 在第二轮中，机器人的选择基于 $s_{pos+1}$。第三轮基于 $s_{pos+2}$，以此类推。走到 $s_n$ 后，机器人会回到 $s_1$ 继续游戏。 你计划进行 $n$ 轮游戏，并且你已经知道了字符串 $s$，但还不知道机器人的起始下标 $pos$。不过，由于机器人的策略太无聊了，你决定为每一轮选择 $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}$ 尽可能大。

第一行包含一个整数 $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$。

对于每个测试用例，输出 $n$ 个选择 $c_1 c_2 \dots c_n$，以最大化平均获胜轮数。输出格式与字符串 $s$ 相同。 如果有多组最优解，输出任意一组即可。

在第一个测试用例中，无论机器人从哪里开始，它总是选择“石头”，所以我们可以一直选择“布”。因此，无论如何我们都能赢下全部 $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$，并且可以证明这是最大可能的平均值。下图来自维基百科，解释了“石头剪刀布”游戏：  由 ChatGPT 4.1 翻译