配点 : $500$ 点

問題文

最強のじゃんけんの手を決めるため、トーナメント形式のじゃんけん大会が開催されます。 大会の参加者は $2^k$ 人で、それぞれ $0$ 以上 $2^k$ 未満の整数が振られています。どの参加者もそれぞれ得意な手を持っていて、毎試合得意な手のみを出します。

参加者の得意な手は、長さ $n$ の R, P, S からなる文字列 $s$ によって表されます。 具体的には、番号 $i$ の参加者の得意な手は $s$ の $(i\text{ mod } 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$ 未満の参加者による大会の勝者の得意な手を求めてください。

注意

• $a\text{ mod } b$ は $a$ を $b$ で割ったあまりを表す
• じゃんけんの勝敗は次のように決められる- 同じ手同士はあいこである
  • R は S に勝つ
  • P は R に勝つ
  • S は P に勝つ
• 同じ手同士はあいこである
• R は S に勝つ
• P は R に勝つ
• S は P に勝つ

制約

• $1 \leq n,k \leq 100$
• $s$ は R, P, S のみからなる長さ $n$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$n$ $k$

$s$

出力

大会の勝者の得意な手を R か P か S で出力せよ。

3 2
RPS

P

• 番号が $0$ 以上 $2$ 未満の参加者による大会の勝者の得意な手は P です。
• 番号が $2$ 以上 $4$ 未満の参加者による大会の勝者の得意な手は R です。
• 番号が $0$ 以上 $4$ 未満の参加者による大会の勝者の得意な手は P です。

よって、答えは P となります。

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

11 1
RPSSPRSPPRS

P

1 100
S

S