問題一覧 > 通常問題

No.3323 Planet Iwai Style Rock-Paper-Scissors

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 56
作問者 : bolero / テスター : ゆにたりー卿 DeltaStruct elphe 👑 loop0919 のらら
お気に入りにしたユーザー ProblemId : 12591 / 自分の提出
問題文最終更新日: 2026-09-04 16:11:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Extra (順位表) の他の問題:

Problem Statement

A rock-paper-scissors tournament is being held on Planet Iwai.
A participant, the Iwaian yiwiy9, plays one match each against each of $N$ Iwaians, using the "Planet Iwai Style Rock-Paper-Scissors" described below.

Rules of Planet Iwai Style Rock-Paper-Scissors
  • Each Iwaian has $M$ hands.
  • Before the tournament, each hand is fixed to one of the shapes rock, scissors, or paper, and the shapes of the hands cannot be changed during the tournament.
  • In a match, starting from the 1st hand and proceeding in order, "ordinary rock-paper-scissors" (rock beats scissors, scissors beats paper, and paper beats rock) is played.
  • As soon as a hand decides the outcome, the player who won becomes the winner of that match, and the match ends.
  • If all the hands result in ties, the result of that match is a draw.

The shapes of the hands of the $i$-th Iwaian ($1 \leq i \leq N$) are given by a string $S_i$ of length $M$.
The $j$-th character ($1 \leq j \leq M$) of $S_i$ is one of G, C, P, which respectively mean that the $j$-th hand of Iwaian $i$ is rock, scissors, or paper.

Through his psychic powers, yiwiy9 knows the shape of each hand of all his opponents before the tournament.
Determine whether there exists a sequence of hands with which yiwiy9 is guaranteed to win against all his opponents, and if one exists, output one example.

Input

$N\ M$
$S_1$
$S_2$
$\vdots$
$S_N$

Constraints

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq N \times M \leq 10^5$
$N, M$ are integers
$S_{i}$ is a string of length $M$ consisting of G, C, P

Output

Determine whether there exists a sequence of hands with which yiwiy9 is guaranteed to win against everyone.
If no such sequence of hands exists, output $-1$.
If one exists, output a string representing those hands.
If there are multiple answers, any of them will be accepted.

Sample

Sample 1
Input
2 3
GGG
CPC
Output
GPG

yiwiy9 and 2 Iwaians participate in the rock-paper-scissors tournament.
The hands of Iwaian 1 have the shapes rock, rock, rock.
The hands of Iwaian 2 have the shapes scissors, paper, scissors.
By making his hands rock, paper, rock, yiwiy9 can win against everyone.
He can also win against all the Iwaians with rock, paper, paper or with rock, paper, scissors.

Sample 2
Input
4 3
PGC
PCP
PPG
GGP
Output
-1

No matter what hands yiwiy9 chooses, he will lose to one of the Iwaians.

Sample 3
Input
4 5
PGCPC
PPGGP
CPGPC
CGCCP
Output
CPPCP

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。