AT_arc109_c.[ARC109C] Large RPS Tournament

为了决定最强的“剪刀石头布”手势，将举办一场锦标赛形式的“剪刀石头布”大赛。参赛者共有 $2^k$ 人，每个人都被分配了一个 $0$ 以上小于 $2^k$ 的整数编号。每位参赛者都有自己擅长的手势，并且每场比赛只会出自己擅长的手势。

参赛者的擅长手势由一个长度为 $n$ 的只包含 R、P、S 的字符串 $s$ 表示。具体来说，编号为 $i$ 的参赛者的擅长手势为 $s$ 的第 $(i\bmod n)+1$ 个字符。其中，R 表示石头，P 表示布，S 表示剪刀。

对于满足 $r-l$ 是 $2$ 的幂的 $l,\ r$，当编号在 $l$ 以上 $r$ 未满的参赛者举办比赛时，胜者的决定方式如下：

• 当 $r-l=1$（即只有一名参赛者时），胜者为 $l$。
• 当 $r-l\geq 2$ 时，令 $m=(l+r)/2$，分别让编号在 $l$ 以上 $m$ 未满和 $m$ 以上 $r$ 未满的参赛者举办比赛。设两边的胜者分别为 $a$ 和 $b$，则 $a$ 和 $b$ 进行“剪刀石头布”，胜者为最终胜者。如果平局，则 $a$ 获胜。

请输出编号为 $0$ 以上 $2^k$ 未满的参赛者举办比赛时，最终胜者的擅长手势（R、P 或 S）。

输入通过标准输入给出，格式如下：

$n$ $k$ $s$

请输出锦标赛最终胜者的擅长手势（R、P 或 S）。

注意

• $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。
• 剪刀石头布的胜负规则如下：
  • 相同手势为平局。
  • R 胜 S。
  • P 胜 R。
  • S 胜 P。

约束条件

• $1\leq n,k\leq 100$
• $s$ 是只包含 R、P、S 的长度为 $n$ 的字符串。

样例解释 1

• 编号 $0$ 以上 $2$ 未满的参赛者举办比赛时，胜者的擅长手势为 P。
• 编号 $2$ 以上 $4$ 未满的参赛者举办比赛时，胜者的擅长手势为 R。
• 编号 $0$ 以上 $4$ 未满的参赛者举办比赛时，胜者的擅长手势为 P。
  因此，答案为 P。

     P
   ┌─┴─┐
  P    R
 ┌┴┐  ┌┴┐
R  P  S  R

由 ChatGPT 4.1 翻译