Недавно, вы обнаружили бота, с которым можно сыграть в «Камень, ножницы, бумага». К сожалению, бот использует довольно примитивный алгоритм игры: у него есть строка $$$s = s_1 s_2 \dots s_{n}$$$ длины $$$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$$$.
Если существует несколько оптимальных ответов, выведите любой из них.
3 RRRR RSP S
PPPP RSP R
В первом наборе входных данных, бот (с какой бы позиции не начал) будет всегда выбирать «Камень», поэтому мы можем всегда выбирать «Бумагу». То есть, в любом случае, мы выиграем все $$$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$$$;
Картинка из Википедии, описывающая игру «Камень, ножницы, бумага»:
