No.3323 Planet Iwai Style Rock-Paper-Scissors
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, POutput
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
bolero
ゆにたりー卿
DeltaStruct
のらら