F - Multiplayer Rock-Paper-Scissors

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点 : 200点

問題文

NN 人の人がいます。i (1iN)i~(1 \leq i \leq N) 番目の人はじゃんけんをするとき、必ず AiA_i の手を出します。

QQ 個のクエリ (クエリ 1,2,,Q1 ,2, \ldots, Q) が与えられるので、それぞれについて答えてください。

  • クエリ ii : 整数 Li,Ri (1Li<RiN)L_i, R_i~(1 \leq L_i < R_i \leq N) が与えられます。 Li,Li+1,,RiL_i, L_i+1, \ldots, R_i 番目の人とあなたで大人数じゃんけんをします。ここで、大人数じゃんけんは次のルールで勝敗を決定します。

    • 1人以上が出した手のうち、出した人数が最も少ない手が1種類のとき、その手を出した人全員が勝ち、それ以外の人は負ける。
    • 1人以上が出した手のうち、出した人数が最も少ない手が2種類のとき、その2種類のうち通常のじゃんけんで勝つ方の手を出した人全員が勝ち、それ以外の人は負ける。
    • 上記以外のとき、全員あいこになる。

    あなたは何の手を出したら勝てますか?勝てる手が存在するならその手をすべて GCP の順番で空白区切りで、存在しないなら -1 を出力してください。

ここで、通常のじゃんけんにおいてグーはチョキに、チョキはパーに、パーはグーにそれぞれ勝つものとします。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • Ai (1iN)A_i~(1 \leq i \leq N)G, C, P のいずれかで、 ii 番目の人はじゃんけんをするとき AiA_iG のときグーを、C のときチョキを、P のときパーを必ず出すことを表す。
  • 1Q2×1051 \leq Q \leq 2 \times 10^5
  • 1Li<RiN1 \leq L_i < R_i \leq N
  • 入力はすべて整数。

入力

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

NN
A1A_1 \ldots ANA_N
QQ
L1L_1 R1R_1
\vdots
LQL_Q RQR_Q

出力

QQ行出力せよ。 ii 行目ではクエリ ii に対する答えを出力せよ。


入出力例1

入力
10
C C G C P C C G G C
3
1 10
1 7
6 8
出力
P
-1
G P
  • クエリ1では、グーを3人、チョキを6人、パーを1人出しています。このとき、あなたはパーを出すことで大人数じゃんけんに勝つことができます。それ以外の手を出すと負けてしまいます。
  • クエリ2では、グーを1人、チョキを5人、パーを1人出しています。このとき、あなたはどんな手を出しても負けてしまうので、-1を出力します。
  • クエリ3では、グーを1人、チョキを2人、パーを0人出しています。このとき、あなたはグーを出してもパーを出しても勝つことができます。よって GP を出力します。複数勝つ手が存在するとき、G C P の順で空白区切りで出力し、最後に改行してください。

入出力例2

入力
20
C G C C G P C G P C G C G C P C P C P C
10
9 15
7 11
15 19
9 18
15 16
2 7
13 14
5 6
6 17
7 16
出力
-1
-1
G C
-1
-1
P
-1
-1
-1
P

提出


Go (1.21)