最近,您发现了一个可以玩“石头剪刀布”的机器人。不幸的是,机器人使用了一个非常简单的算法来玩:他有一个字符串 $$$s = s_1 s_2 \dots s_{n}$$$,长度为 $$$n$$$,其中每个字母是 R、S 或 P。
初始化时,机器人选择起始索引 $$$pos$$$ ($$$1 \le pos \le n$$$),然后它可以玩任意轮数。第一轮,他根据$$$s_{pos}$$$的值选择“石头”、“剪刀”或“布”:
- 如果 $$$s_{pos}$$$ 等于 R,机器人选择“Rock”;
- 如果 $$$s_{pos}$$$ 等于 S,机器人选择“剪刀”;
- 如果 $$$s_{pos}$$$ 等于 P,机器人选择“Paper”;
在第二轮中,机器人的选择基于 $$$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$$$ 相同的方式打印它们。
如果有多个最佳答案,则打印其中任何一个。
示例
输入 #1
3 RRRR RSP S
输出 #1
PPPP RSP R
注意
在第一个测试用例中,机器人(无论它从哪里开始)将始终选择“Rock”,因此我们始终可以选择“Paper”。因此,无论如何,我们都会赢得所有 $$$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$$$;
一张来自维基百科的图片解释“剪刀石头布”游戏: