AT_arc109_c [ARC109C] Large RPS Tournament

[problemUrl]: https://atcoder.jp/contests/arc109/tasks/arc109_c 最強のじゃんけんの手を決めるため、トーナメント形式のじゃんけん大会が開催されます。 大会の参加者は $ 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 $ 未満の参加者による大会の勝者の得意な手を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ k $ $ s $

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

### 注意 - $ a\text{\ mod\ }\ b $ は $ a $ を $ b $ で割ったあまりを表す - じゃんけんの勝敗は次のように決められる - 同じ手同士はあいこである - `R` は `S` に勝つ - `P` は `R` に勝つ - `S` は `P` に勝つ ### 制約 - $ 1\ \leq\ n,k\ \leq\ 100 $ - $ s $ は `R`, `P`, `S` のみからなる長さ $ n $ の文字列 ### Sample Explanation 1 \- 番号が $ 0 $ 以上 $ 2 $ 未満の参加者による大会の勝者の得意な手は `P` です。 - 番号が $ 2 $ 以上 $ 4 $ 未満の参加者による大会の勝者の得意な手は `R` です。 - 番号が $ 0 $ 以上 $ 4 $ 未満の参加者による大会の勝者の得意な手は `P` です。 よって、答えは `P` となります。 ``` P ┌─┴─┐ P R ┌┴┐ ┌┴┐ R P S R ```