Недавно, вы обнаружили бота, с которым можно сыграть в «Камень, ножницы, бумага». К сожалению, бот использует довольно примитивный алгоритм игры: у него есть строка \(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}\) — максимально возможное.
Выходные данные
Для каждого набора входных данных, выведите \(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\), и можно доказать, что это максимально возможное среднее количество побед.
Картинка из Википедии, описывающая игру «Камень, ножницы, бумага»:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
RRRR
RSP
S
|
PPPP
RSP
R
|